Portal (Codeforces 1580A)
Tags: Greedy, data structures

CQXYM found a rectangle $$$A$$$ of size $$$n \times m$$$. There are $$$n$$$ rows and $$$m$$$ columns of blocks. Each block of the rectangle is an obsidian block or empty. CQXYM can change an obsidian block to an empty block or an empty block to an obsidian block in one operation.A rectangle $$$M$$$ size of $$$a \times b$$$ is called a portal if and only if it satisfies the following conditions:  $$$a \geq 5,b \geq 4$$$.  For all $$$1 < x < a$$$, blocks $$$M_{x,1}$$$ and $$$M_{x,b}$$$ are obsidian blocks.  For all $$$1 < x < b$$$, blocks $$$M_{1,x}$$$ and $$$M_{a,x}$$$ are obsidian blocks.  For all $$$1<x<a,1<y<b$$$, block $$$M_{x,y}$$$ is an empty block.  $$$M_{1, 1}, M_{1, b}, M_{a, 1}, M_{a, b}$$$ can be any type.  Note that the there must be $$$a$$$ rows and $$$b$$$ columns, not $$$b$$$ rows and $$$a$$$ columns.Note that corners can be any typeCQXYM wants to know the minimum number of operations he needs to make at least one sub-rectangle a portal.

Input: The first line contains an integer $$$t$$$ ($$$t \geq 1$$$), which is the number of test cases.For each test case, the first line contains two integers $$$n$$$ and $$$m$$$ ($$$5 \le n \le 400$$$, $$$4 \le m \le 400$$$). Then $$$n$$$ lines follow, each line contains $$$m$$$ characters $$$0$$$ or $$$1$$$. If the $$$j$$$-th character of $$$i$$$-th line is $$$0$$$, block $$$A_{i,j}$$$ is an empty block. Otherwise, block $$$A_{i,j}$$$ is an obsidian block.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$400$$$.It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$400$$$.

Output: Output $$$t$$$ answers, and each answer in a line.

Note: In the first test case, the final portal is like this:11101001100110010111

Sample Inputs:
1
5 4
1000
0000
0110
0000
0001

1
9 9
001010001
101110100
000010011
100000001
101010101
110001111
000001111
111100000
000110000

Sample Outputs:
12

5

Solution (Python):
import sys
sys.setrecursionlimit(100000)

def _r():
    return sys.stdin.buffer.readline()

def rs():
    return _r().decode('ascii').strip()

def rn():
    return int(_r())

def rnt():
    return tuple(map(int, _r().split()))

def rnl():
    return list(rnt())
from itertools import accumulate

def solve(n, m, aa):
    best = 16
    och = [list(accumulate(ar)) for ar in aa]
    ocv = [list(accumulate(ac)) for ac in zip(*aa)]
    ob = [list(accumulate(v)) for v in zip(*ocv)]
    for i in range(n - 4):
        for j in range(m - 3):
            for k in range(i + 4, n):
                leftc = k - i - 1 - ocv[j][k - 1] + ocv[j][i]
                if leftc >= best:
                    break
                for l in range(j + 3, m):
                    rightc = k - i - 1 - ocv[l][k - 1] + ocv[l][i]
                    topc = l - j - 1 - och[i][l - 1] + och[i][j]
                    bottomc = l - j - 1 - och[k][l - 1] + och[k][j]
                    ic = ob[k - 1][l - 1] - ob[k - 1][j] - ob[i][l - 1] + ob[i][j]
                    if leftc + topc + ic >= best:
                        break
                    cost = leftc + rightc + topc + bottomc + ic
                    best = min(cost, best)
    return best
for _ in range(rn()):
    (n, m) = rnt()
    mat = []
    for _ in range(n):
        mat.append(list(map(int, rs())))
    print(solve(n, m, mat))

Solution (Python):
import sys
input = sys.stdin.readline
(T,) = map(int, input().split())
for _ in range(T):
    (N, M) = map(int, input().split())
    X = [[0] * (M + 1)]
    for _ in range(N):
        X.append([0] + [int(c) for c in input().strip()])
    Y = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        for j in range(M + 1):
            Y[i][j] = X[i][j]
    for i in range(1, N + 1):
        for j in range(1, M + 1):
            X[i][j] += -X[i - 1][j - 1] + X[i][j - 1] + X[i - 1][j]
    R = 10 ** 18
    L = []
    for i in range(5, N + 1):
        for j in range(4, M + 1):
            x = i - 4
            y = j - 3
            r = X[i - 1][j - 1] - X[x][j - 1] - X[i - 1][y] + X[x][y]
            rrr = X[i - 1][j] + X[i][j - 1] - X[i - 1][j - 1] - r - (X[x - 1][j] + X[i][y - 1] - X[x - 1][y - 1])
            r2 = rrr - Y[x][j] - Y[i][y] - Y[x][y]
            rr = r + (2 * (i - x + 1 - 2) + 2 * (j - y + 1 - 2)) - r2
            L.append((rr, x, y))
    L.sort(key=lambda x: x[0])
    for i in range(min(len(L), 23)):
        (_, x, y) = L[i]
        for i in range(x + 4, N + 1):
            for j in range(y + 3, M + 1):
                r = X[i - 1][j - 1] - X[x][j - 1] - X[i - 1][y] + X[x][y]
                rrr = X[i - 1][j] + X[i][j - 1] - X[i - 1][j - 1] - r - (X[x - 1][j] + X[i][y - 1] - X[x - 1][y - 1])
                r2 = rrr - Y[x][j] - Y[i][y] - Y[x][y]
                rr = r + (2 * (i - x + 1 - 2) + 2 * (j - y + 1 - 2)) - r2
                if R > rr:
                    R = rr
    print(R)

Solution (Python):
from sys import *

def preProcess(mat, aux, N, M):
    for i in range(0, M, 1):
        aux[0][i] = mat[0][i]
    for i in range(1, N, 1):
        for j in range(0, M, 1):
            aux[i][j] = mat[i][j] + aux[i - 1][j]
    for i in range(0, N, 1):
        for j in range(1, M, 1):
            aux[i][j] += aux[i][j - 1]

def sumQuery(aux, tli, tlj, rbi, rbj):
    res = aux[rbi][rbj]
    if tli > 0:
        res = res - aux[tli - 1][rbj]
    if tlj > 0:
        res = res - aux[rbi][tlj - 1]
    if tli > 0 and tlj > 0:
        res = res + aux[tli - 1][tlj - 1]
    return res
lim = 10000000
for _ in range(int(stdin.readline())):
    (n, m) = map(int, stdin.readline().split())
    a = []
    for i in range(n):
        tmp = stdin.readline()
        a.append([])
        for j in range(m):
            a[i].append(int(tmp[j]))
    aux = [[0 for i in range(m)] for j in range(n)]
    preProcess(a, aux, n, m)
    ans = 16
    if n * m * n * m <= lim:
        for i in range(n - 4):
            for j in range(m - 3):
                for row in range(i + 4, n):
                    for col in range(j + 3, m):
                        topleft = [i, j]
                        downleft = [row, j]
                        topright = [i, col]
                        downright = [row, col]
                        top = sumQuery(aux, topleft[0], topleft[1] + 1, topright[0], topright[1] - 1)
                        down = sumQuery(aux, downleft[0], downleft[1] + 1, downright[0], downright[1] - 1)
                        left = sumQuery(aux, topleft[0] + 1, topleft[1], downleft[0] - 1, downleft[1])
                        right = sumQuery(aux, topright[0] + 1, topright[1], downright[0] - 1, downright[1])
                        center = sumQuery(aux, topleft[0] + 1, topleft[1] + 1, downright[0] - 1, downright[1] - 1)
                        curr = center
                        curr += topright[1] - topleft[1] - 1 - top
                        curr += topright[1] - topleft[1] - 1 - down
                        curr += downleft[0] - topleft[0] - 1 - left
                        curr += downleft[0] - topleft[0] - 1 - right
                        ans = min(ans, curr)
        stdout.write(str(ans) + '\n')
    else:
        for i in range(n - 4):
            for j in range(m - 3):
                for row in range(i + 4, min(n, i + 9)):
                    for col in range(j + 3, min(m, j + 8)):
                        topleft = [i, j]
                        downleft = [row, j]
                        topright = [i, col]
                        downright = [row, col]
                        top = sumQuery(aux, topleft[0], topleft[1] + 1, topright[0], topright[1] - 1)
                        down = sumQuery(aux, downleft[0], downleft[1] + 1, downright[0], downright[1] - 1)
                        left = sumQuery(aux, topleft[0] + 1, topleft[1], downleft[0] - 1, downleft[1])
                        right = sumQuery(aux, topright[0] + 1, topright[1], downright[0] - 1, downright[1])
                        center = sumQuery(aux, topleft[0] + 1, topleft[1] + 1, downright[0] - 1, downright[1] - 1)
                        curr = center
                        curr += topright[1] - topleft[1] - 1 - top
                        curr += topright[1] - topleft[1] - 1 - down
                        curr += downleft[0] - topleft[0] - 1 - left
                        curr += downleft[0] - topleft[0] - 1 - right
                        ans = min(ans, curr)
        for i in range(n - 4):
            for j in range(m - 3):
                for row in range(n - 1, n - 2, -1):
                    for col in range(m - 1, m - 2, -1):
                        topleft = [i, j]
                        downleft = [row, j]
                        topright = [i, col]
                        downright = [row, col]
                        top = sumQuery(aux, topleft[0], topleft[1] + 1, topright[0], topright[1] - 1)
                        down = sumQuery(aux, downleft[0], downleft[1] + 1, downright[0], downright[1] - 1)
                        left = sumQuery(aux, topleft[0] + 1, topleft[1], downleft[0] - 1, downleft[1])
                        right = sumQuery(aux, topright[0] + 1, topright[1], downright[0] - 1, downright[1])
                        center = sumQuery(aux, topleft[0] + 1, topleft[1] + 1, downright[0] - 1, downright[1] - 1)
                        curr = center
                        curr += topright[1] - topleft[1] - 1 - top
                        curr += topright[1] - topleft[1] - 1 - down
                        curr += downleft[0] - topleft[0] - 1 - left
                        curr += downleft[0] - topleft[0] - 1 - right
                        ans = min(ans, curr)
        stdout.write(str(ans) + '\n')