PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy-Medium
PREREQUISITES:
None
PROBLEM:
There’s a 2\times 2 grid A. Alice and Bob play a game on it, alternating turns. Alice goes first.
On their turn, a player must select a cell (i, j) and remove one stone from it.
However, the chosen cell must share either a row or a column (or both) from the previously chosen cell.
The first cell can be chosen freely.
The game ends when making a move is impossible, i.e. no cell in the same row or column has a positive number of stones.
Alice wants to maximize the number of remaining stones, while Bob wants to minimize it.
Find the number of stones that will remain under optimal play.
EXPLANATION:
Let’s first understand when the game ends.
Suppose the last move was made at cell (1, 1).
Then, the next move is impossible to make only when all three of (1, 1), (1, 2), (2, 1) have no remaining stones.
Going one step further, observe that to reach such a state, the only possible way is to have cells (1, 2) and (2, 1) both have zero stones, the the last move must be made on one of these two cells - this then forces the next player to choose either (1, 1) or (2, 2) and then the players cannot move out of the chosen cell.
By symmetry, this obviously applies to every other cell too.
That is, generalizing the above idea, it can be seen that for the game to end, one diagonal of the grid must have both its elements be zeros; and then the next player is forced to choose an element on the other diagonal - the chosen element becomes zero, while the other element remains in full.
Clearly, the diagonals are important here.
Alice wants to maximize the remaining element, so it’s in her best interest to make one diagonal 0 as soon as possible.
Bob on the other hand would like to not make any diagonal 0, since then he can keep on reducing elements further.
In particular, it can be proven that the only time Bob is forced to make a diagonal 0 himself is when the grid looks like \begin{bmatrix} 0 & x \\ 0 & 1 \end{bmatrix} (or some rotation of this); and in this case it’s easy to see that in the end all the stones are going to be removed anyway so the answer is 0 (which is optimal for Bob.)
Thus, we can assume that without loss of generality, the first one to make a diagonal 0 will be Alice.
Now, suppose Alice makes the diagonal consisting of A_{1, 1} and A_{2, 2} both 0.
Bob will then choose to move to \max(A_{1, 2}, A_{2, 1}) so that this element goes to 0, and only \min(A_{1, 2}, A_{2, 1}) remains.
However, Alice must make A_{1, 1} + A_{2, 2} moves to remove all the stones from her chosen diagonal; and Bob can make moves after each of those too.
For these moves of Bob, it’s clear that it’s optimal to minimize \min(A_{1, 2}, A_{2, 1}) since that’s the remaining value.
So, for each of the first (A_{1, 1} + A_{2, 2} - 1) moves of Alice, Bob will subtract 1 from \min(A_{1, 2}, A_{2, 1}).
Then, for Alice’s last move, Bob will move to \max(A_{1, 2}, A_{2, 1}) instead, and that value goes to 0 entirely too.
Thus, if Alice makes the diagonal of (A_{1, 1}, A_{2, 2}) zeros, the final number of remaining stones will equal
\max(0, \min(A_{1, 2}, A_{2, 1}) - (A_{1, 1} + A_{2, 2} - 1))
Similarly, applying this analysis to the other diagonal shows that if Alice chooses to make that one 0 instead, the remaining value will be
\max(0, \min(A_{1, 1}, A_{2, 2}) - (A_{1, 2} + A_{1, 2} - 1))
Alice will choose the maximum of these two quantities.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
def solve(a, b, c, d):
s1 = a + d
s2 = b + c
return max(max(0, min(b, c) - s1 + 1), max(0, min(a, d) - s2 + 1))
for _ in range(int(input())):
a, b, c, d = map(int, input().split())
print(solve(a, b, c, d))