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)
