mm107 PointsOnGrid IP Solver

PointsOnGrid.py

from __future__ import print_function
from ortools.linear_solver import pywraplp
from functools import reduce
import sys
import time

class PointsOnGrid:
    def findSolution(self, H, W, h, w, Kmin, Kmax, grid):
        solver = pywraplp.Solver('SolveIntegerProblem',
            pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

        s = [[ord(a) - ord('0') for a in s] for s in grid]
        s = reduce(lambda a, b: a+b, s)

        x = [solver.IntVar(0.0, 1.0, 'x_{}_{}'.format(i//W, i%W)) for i, z in enumerate(s)]
        constraints = []
        for i in range(H-h+1):
            for j in range(W-w+1):
                cmax = solver.Constraint(-solver.infinity(), Kmax)
                for di in range(H):
                    for dj in range(W):
                        z = di * W + dj
                        if di - i < h and dj - j < w and di - i >= 0 and dj - j >= 0:
                            cmax.SetCoefficient(x[z], 1)
                        else:
                            cmax.SetCoefficient(x[z], 0)
                constraints.append(cmax)

                cmin = solver.Constraint(-solver.infinity(), -Kmin)
                for di in range(H):
                    for dj in range(W):
                        z = di * W + dj
                        if di - i < h and dj - j < w and di - i >= 0 and dj - j >= 0:
                            cmin.SetCoefficient(x[z], -1)
                        else:
                            cmin.SetCoefficient(x[z], 0)
                constraints.append(cmin)

        objective = solver.Objective()
        for i in range(H * W):
            objective.SetCoefficient(x[i], s[i])

        objective.SetMaximization()

        solver.set_time_limit(9000)

        start_time = time.time();
        result_status = solver.Solve()
        end_time = time.time();

        if result_status == pywraplp.Solver.OPTIMAL:
            print("optimal.", file=sys.stderr)
        else:
            print("time out.", file=sys.stderr)

        print("time = {} [sec]".format(end_time - start_time), file=sys.stderr)

        ret = []
        for i in range(H):
            a = ''
            for j in range(W):
                z = i*W + j;
                a += "x" if x[z].solution_value() == 1 else "."
                # a += str(x[z].solution_value())
            ret.append(a)

        return ret

# -------8<------- end of solution submitted to the website -------8<-------

import sys
H = int(input())
W = int(input())
h = int(input())
w = int(input())
Kmin = int(input())
Kmax = int(input())
grid_size = int(input())
grid = []
for i in range(H):
    grid.append(input())

pog = PointsOnGrid()
ret = pog.findSolution(H, W, h, w, Kmin, Kmax, grid)
print(len(ret))
for st in ret:
    print(st)
sys.stdout.flush()

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17405&pm=15265

IP Solver (OR-Tools + CBC) for MM107 PointsOnGrid

99% cases can be solved (optimal) within 10 sec.
I tried 1000 seeds. 993 / 1000 seeds were optimal.
Try it to check your scores.

Please install OR-Tools beforehand.

// install OR-Tools
python -m pip install -U --user ortools

// run
python PointsOnGrid.py < INPUT

// run with java tester (tester.jar)
java -jar tester.jar -exec "python PointsOnGrid.py" -seed <seed>

// run with java tester (PointsOnGridVis.java)
java PointsOnGridVis -exec "python PointsOnGrid.py" -seed <seed>