SMXR - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N and M, both even, define F(K) to be the minimum possible sum of \sum_{i=1}^N R_i + \sum_{i=1}^M C_i across all N\times M boolean grids containing exactly K ones.
R_i denotes the bitwise XOR of the i-th row, and C_i denotes the bitwise XOR of the i-th column.

Find \displaystyle\sum_{K=1}^{NM} F(K).

EXPLANATION:

First, we of course need to figure out what F(K) actually is.

If K is a multiple of 4, we always have F(K) = 0.
This is because the N\times M grid can be tiled with 2\times 2 subgrids (since N and M are both even), and taking some \frac{K}{4} of these subgrids will give us K ones while also ensuring that every row and every column has an even number of ones; hence each R_i and C_i will be 0.

This observation also tells us that it might be helpful to look at values of K modulo 4, so we do exactly that.

  • If K = 4x, F(K) = 0 as noted above.
  • If K = 4x+1, F(K) = 2.
    We can place 4x ones using the above strategy, which leaves us with a single extra.
    Anywhere it’s placed, that row and column will have an odd number of ones; giving a sum of 2.
    • It’s further not hard to see that 2 is optimal, because having an odd number of ones in total means some row and some column must contain an odd number of ones.
  • Similarly, if K = 4x+3, we have F(K) = 2 again.
    Place 4x ones in 2\times 2 blocks, then choose any 2\times 2 block and fill in three of its slots. This leaves one row and one column with an odd number of ones.

That only leaves the K = 4x+2 case.
For this, observe that we certainly have F(K) \leq 2 - using the same strategy as above, we can fill in 4x cells using 2\times 2 subgrids, then fill in two adjacent cells in another subgrid.
However, we can sometimes do better!


When N = 2 or M = 2, we don’t really have enough space for more fancy arrangements.
In these cases, indeed F(K) = 2 when K is 2 modulo 4.

Proof

Without loss of generality, let N = 2.

If every column contains either 0 or 2 ones, the number of ones in the first and second row must be equal.
But there are 4x+2 ones in total, meaning 2x+1 in each row (which is odd).
So, R_1 + R_2 = 2 while all the C_i are 0.

On the other hand, if some column contains exactly one 1, there must be at least one more column containing exactly one 1 (since the total number of ones is even).
In this case, the value of the grid is at least 2.

So, when N = 2, we have F(K) = 2 when K = 4x+2.
M = 2 is similar, just flip the dimensions.

Now, suppose N, M\geq 4.
If K = 2, then the best we can do is place both ones in the same row or column; giving F(2) = 2.
Similarly, if K = N\cdot M - 2, the best we can do is remove two ones from the same row/column, giving a value of 2 again.
In every other case, we in fact have F(K) = 0.

How?

For this, it’s helpful to look at the case N = M = 4.

Observe that for K = 6 and K = 10, we have the following arrangements:

1100
0110
1010
0000
1111
1100
1010
1001

These ensure that every row and column has an even number of ones.

Now, for an arbitrary N, M, K (where N, M \geq 4 and 2 \lt K \lt N\cdot M - 2), do the following:

  • If K = 6 or K = 10, use the above strategies to obtain a value of 0.
    We’re now left with K \gt 10.
  • Keep the top-left 4\times 4 grid aside for now.
    The remainder of the grid can be tiled using \frac{NM}{4} - 4 subgrids of size 2\times 2.
  • Repeatedly keep filling in these 2\times 2 grids till you need to place 10 ones.
    Then, place these 10 ones in the top-left 4\times 4 grid in the above pattern.

Finally, we need to actually sum this up across all K.
However, since every value is either 0 or 2, that’s actually quite simple.

  • If N = 2 or M = 2, we have F(K) = 0 when K is a multiple of 4, and F(K) = 2 otherwise.
    Summing this up across all K gives \displaystyle 2\cdot \frac{3NM}{4} = \frac{3NM}{2}
  • If N, M \geq 4, we have F(K) = 2 for every odd K, and K = 2 and N\cdot M - 2.
    That gives us a value of \displaystyle 2\cdot\frac{NM}{2} + 4 = NM + 4.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    n, m = map(int, input().split())
    if n == 2 or m == 2:
        print((3*n*m)//2)
    else:
        print(n*m + 4)
3 Likes

Not able to understand the explanation :neutral_face:

2 Likes

The same.


n=4, m=4. k=6,f(k)=0

2 Likes

Thanks for the reply. Now i understood :grinning: