Get ready.

python3

import numpy as np, networkx as nx
from pulp import *
def addvar(lowBound=0, var_count=[0], *args, **kwargs):
    """Variable creation utility"""
    var_count[0] += 1
    return LpVariable('v%d' % var_count[0], lowBound=lowBound, *args, **kwargs)
def calc(a, r):
    """Calculate the amount of acquired data with r as the installation location"""
    b = a.copy()
    b[b > 1] = 0
    for x, y in r:
        b[y, x] = 1
    s = b.sum() * 3
    for y in range(0, b.shape[0], 2):
        for x in range(b.shape[1]):
            s -= 2 * b[y, x] * b[y+1,x]
            if x:
                s -= 2 * b[y, x] * b[y+1,x-1]
            if y:
                s -= 2 * b[y, x] * b[y-1,x]
    return s

solve_by_mip is a MIP solution. Returns the installation location.

python3

def solve_by_mip(a):
    """Solve the problem with MIP and return the installation location"""
    nm, nn = a.shape
    b = a.astype(object)
    vv1 = [addvar(cat=LpBinary) for _ in range((b > 1).sum())]
    b[b > 1] = vv1
    vv2 = []
    m = LpProblem(sense=LpMaximize)
    for y in range(0, nm, 2):
        for x in range(nn):
            chk(m, vv2, b[y,x] + b[y+1,x])
            if x: chk(m, vv2, b[y,x] + b[y+1,x-1])
            if y: chk(m, vv2, b[y,x] + b[y-1,x])
    m += 3 * lpSum(vv1) - 2 * lpSum(vv2)
    m.solve()
    return [(x, y) for x in range(nn) for y in range(nm)
            if isinstance(b[y,x], LpVariable) and value(b[y, x]) > 0.5]
def chk(m, vv2, e):
    """If e contains a variable, add a constraint that reduces the objective function by 2 if both are 1."""
    if isinstance(e, LpAffineExpression):
        v = addvar()
        vv2.append(v)
        m += e - v <= 1

solve_by_graph is a minimum cut solution. Also return the installation location.

python3

def solve_by_graph(a):
    """Solve the problem with the minimum cut problem and return the installation location"""
    nm, nn = a.shape
    g = nx.DiGraph()
    for y in range(0, nm, 2):
        for x in range(nn):
            if a[y, x] == 0: # off
                g.add_edge('s', (x,y), capacity=7)
            elif a[y, x] == 1: # on
                g.add_edge((x,y), 't', capacity=7)
            else:
                g.add_edge('s', (x,y), capacity=0)
                g.add_edge((x,y), 't', capacity=3)
            if a[y+1, x] == 0: # off
                g.add_edge((x,y+1), 't', capacity=7)
            elif a[y+1, x] == 1: # on
                g.add_edge('s', (x,y+1), capacity=7)
            else:
                g.add_edge('s', (x,y+1), capacity=3)
                g.add_edge((x,y+1), 't', capacity=0)
            g.add_edge((x,y+1), (x,y), capacity=2)
            if x:
                g.add_edge((x-1,y+1), (x,y), capacity=2)
            if y:
                g.add_edge((x,y-1), (x,y), capacity=2)
    r = []
    for s in nx.minimum_cut(g, 's', 't')[1]:
        b = 's' in s
        for t in s:
            if isinstance(t, str): continue
            x, y = t
            if a[y, x] > 1 and b == (y%2 != 0):
                r.append((x, y))
    return sorted(r)

Let's compare the results by randomly setting fixed points in a size of 40 x 80.

python3

nn, nm = 40, 80 #Horizontal, vertical
np.random.seed(1)
a = np.random.randint(0, 6, (nm, nn)) # 0; fix off, 1: fix on, ow:select

%time rmip = calc(a, solve_by_mip(a))
%time rgrp = calc(a, solve_by_graph(a))
print(rmip == rgrp)
>>>
Wall time: 455 ms
Wall time: 185 ms

True

――You can see that both methods have the same amount of acquired data (rmip == rgrp). --MIP is more than twice as slow. --In general, the dedicated solver is faster than the general-purpose solver. ――When I confirmed it separately, the calculation time of the MIP solver alone was slightly longer than the calculation time of the minimum cut. ――Although the theory is unknown, the amount of acquired data does not change even if MIP is linearly relaxed, and the calculation time is slightly faster.

Reference site

-Problem E. The Year of Code Jam: Referenced issue -Solve the "burn fill problem" using the minimum cut: Referenced solution

that's all