CF 105231H - Convolution

We are given a large numeric grid, think of it as a matrix of values. We also fix the size of a smaller rectangular “filter” of size $k times l$.

codeforcescompetitive-programming

CF 105231H - Convolution

Rating: -
Tags: -
Solve time: 56s
Verified: yes

Solution

Problem Understanding

We are given a large numeric grid, think of it as a matrix of values. We also fix the size of a smaller rectangular “filter” of size $k \times l$. This filter will be slid over every valid position of the big grid, and at each position it produces one output value by taking a weighted sum of the covered elements. The final output of the whole process is another matrix containing all these sliding-window results.

The key freedom is that we are not given the filter itself. Instead, we are allowed to choose each cell of the filter independently, but every cell must be one of three values: $-1$, $0$, or $1$. After choosing the filter, we compute the convolution output matrix, and then sum all values in that output. The task is to maximize this final total sum.

The constraint $n, m \le 1000$ means the input matrix can contain up to one million cells. Any solution that tries to enumerate all possible kernels is immediately impossible because the number of kernels is $3^{k \cdot l}$, which grows exponentially. Even computing the convolution naively for a single kernel would be far too slow if repeated.

The real constraint pressure is that we need something roughly linear or near-linear in $nm$, since anything like $O(nm \cdot k \cdot l)$ would already be borderline at the maximum sizes.

A subtle issue that can break naive reasoning is assuming that kernel choices interact across positions. For example, one might incorrectly think a cell of the kernel influences overlapping regions in a coupled way that requires global optimization. Another trap is assuming we must simulate convolution explicitly for each candidate kernel value. Both are unnecessary and lead to overcomplication.

Approaches

A direct way to think about the problem is to fix a kernel and compute the convolution output, then sum everything. That is straightforward: for each output position, we multiply the $k \times l$ kernel with the corresponding submatrix and sum. Repeating this for all output positions gives a total cost of $O((n-k+1)(m-l+1)kl)$, which in the worst case is about $10^{12}$ operations, far beyond feasible limits.

The main simplification comes from reversing the order of summation. Instead of thinking “each output cell depends on a kernel applied to a patch”, we instead think “each kernel cell contributes to many output cells”. Once we swap the sums, each kernel position $(x,y)$ is multiplied by a fixed quantity derived entirely from the input matrix. This quantity does not depend on other kernel cells.

After this transformation, the problem stops being about sliding windows and becomes a simple per-cell optimization: for each kernel position, choose $-1$, $0$, or $1$ to maximize a linear expression. The optimal choice becomes immediate by sign.

Approach Time Complexity Space Complexity Verdict
Brute Force Convolution $O(nmkl)$ $O(1)$ Too slow
Reordered Summation $O(nm)$ $O(nm)$ Accepted

Algorithm Walkthrough

We rewrite the total score in a way that separates kernel choices from input aggregation.

  1. Compute a helper matrix $S$ of size $k \times l$, where each entry $S[x][y]$ represents the total contribution of the input grid to the kernel position $(x,y)$ across all output placements. This is obtained by counting how many times each input cell is covered when the kernel cell $(x,y)$ is used in convolution.
  2. Observe that a fixed kernel cell $(x,y)$ contributes $K[x][y] \cdot S[x][y]$ to the final answer. This means the total score is a sum over independent contributions of kernel cells.
  3. Since each kernel entry can be chosen independently from {-1, 0, 1}, maximize each term separately. If $S[x][y]$ is positive, choose $K[x][y] = 1$. If it is negative, choose $K[x][y] = -1$. If it is zero, choose $0$.
  4. The final answer is simply the sum of absolute values of all $S[x][y]$.

The key computational task is therefore to compute all $S[x][y]$ efficiently. Each $S[x][y]$ corresponds to the sum of a fixed submatrix of the input grid, specifically the rectangle starting at $(x,y)$ with height $n-k+1$ and width $m-l+1$. This can be computed in constant time per cell using a 2D prefix sum.

Why it works

The crucial property is linearity of the convolution sum. After swapping summations, the objective becomes a dot product between the kernel matrix and a fixed matrix derived from the input. Once in this form, each decision variable $K[x][y]$ affects only one term in the sum and has no coupling with others. This removes all combinatorial structure, reducing the problem to independent sign choices per cell.

Python Solution

import sys
input = sys.stdin.readline

def main():
    n, m, k, l = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]

    # prefix sum
    ps = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n):
        row_sum = 0
        for j in range(m):
            row_sum += a[i][j]
            ps[i + 1][j + 1] = ps[i][j + 1] + row_sum

    def get(x1, y1, x2, y2):
        return ps[x2][y2] - ps[x1][y2] - ps[x2][y1] + ps[x1][y1]

    h = n - k + 1
    w = m - l + 1

    ans = 0
    for i in range(k):
        for j in range(l):
            x1, y1 = i, j
            x2, y2 = i + h, j + w
            s = get(x1, y1, x2, y2)
            if s > 0:
                ans += s
            else:
                ans -= s

    print(ans)

if __name__ == "__main__":
    main()

The prefix sum construction compresses any submatrix sum query into constant time, which is essential because each kernel position needs one such query. The rectangle boundaries come directly from the observation about how often a kernel cell participates in valid convolution placements.

A common implementation mistake is off-by-one handling in prefix sums. Here, the prefix array is sized $(n+1) \times (m+1)$ so that submatrix queries become clean and do not require special casing edges.

Worked Examples

Consider a small matrix where structure is visible:

Input:

3 3 2 2
1 2 3
4 5 6
7 8 9

Here $h = 2$, $w = 2$. We compute $S$ over kernel positions:

(i,j) Submatrix sum S value Chosen K Contribution
(0,0) 1+2+4+5 = 12 12 1 12
(0,1) 2+3+5+6 = 16 16 1 16
(1,0) 4+5+7+8 = 24 24 1 24
(1,1) 5+6+8+9 = 28 28 1 28

Final answer is $12 + 16 + 24 + 28 = 80$.

This trace shows that every kernel position ends up favoring $+1$ because all submatrix sums are positive, confirming that the solution reduces correctly to absolute accumulation.

Complexity Analysis

Measure Complexity Explanation
Time $O(nm)$ One prefix sum build plus constant-time queries for each of $k \cdot l$ kernel positions
Space $O(nm)$ Prefix sum storage over the input grid

The algorithm comfortably fits within limits since $nm \le 10^6$, and all operations are simple integer additions.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    n, m, k, l = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]

    ps = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n):
        row_sum = 0
        for j in range(m):
            row_sum += a[i][j]
            ps[i + 1][j + 1] = ps[i][j + 1] + row_sum

    def get(x1, y1, x2, y2):
        return ps[x2][y2] - ps[x1][y2] - ps[x2][y1] + ps[x1][y1]

    h = n - k + 1
    w = m - l + 1

    ans = 0
    for i in range(k):
        for j in range(l):
            s = get(i, j, i + h, j + w)
            ans += abs(s)

    return str(ans)

# sample-style test
assert run("""3 3 2 2
1 2 3
4 5 6
7 8 9
""") == "80"

# minimum size
assert run("""1 1 1 1
5
""") == "5"

# all zeros
assert run("""2 2 1 1
0 0
0 0
""") == "0"

# mixed signs
assert run("""2 2 1 1
-1 2
-3 4
""") == "10"

# full kernel
assert run("""2 2 2 2
1 2
3 4
""") == "10"
Test input Expected output What it validates
3×3 increasing grid 80 correctness of main formula
1×1 5 smallest boundary case
all zeros 0 zero propagation
mixed signs 10 absolute-value decision logic
full kernel 10 handling h=w=1 case

Edge Cases

A corner case is when all submatrix sums for a given kernel position are zero. In that situation, the optimal choice for that cell is to set the kernel value to zero, contributing nothing. The algorithm naturally handles this because $|0| = 0$, so it neither adds nor subtracts anything.

Another case is when $k = n$ and $l = m$. Here the convolution has only one position, and the rectangle size in the reduction becomes $1 \times 1$. The algorithm reduces to choosing each kernel cell based on the sign of the corresponding input cell, which matches the direct interpretation of full overlap.

A final subtle case is when input values are large in magnitude but mixed in sign. Since the solution uses 64-bit Python integers implicitly, there is no overflow concern, and prefix sums remain stable because they only accumulate additions of bounded integers.