Editorial for Yet Another Contest 6 P4 - No More Nails!

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: Josh, RandomLB

Subtask 1

For subtask 1, we can only add a board with side length $1$ ~1~. Since no moves can be made on such a board, adding one is equivalent to not adding any board. So, we just need to find the winner if Mike and Nils were to play on the given board. If Nils is the winner, then we cannot change this, so there is no valid solution. If Mike is already the winner, then we just add a board of side length $1$ ~1~.

To determine the winner, we can use dynamic programming. Consider the state where the board has $a$ ~a~ rows and $b$ ~b~ columns, and the nail is $c$ ~c~ rows from the top and $d$ ~d~ columns from the left. Define $dp[a][b][c][d] = 1$ ~dp[a][b][c][d] = 1~ if it is a winning state, and $0$ ~0~ if it is a losing state. Recall that a state is a winning state if can transition to a losing state, and a losing state otherwise. It suffices to try each possible transition at each state.

Time complexity: $\mathcal{O}(\max(s_i)^5)$ ~\mathcal{O}(\max(s_i)^5)~

Subtask 2

As in subtask 1, adding a board of side length $1$ ~1~ has no effect, so we can all we have to determine is whether or not Mike can win using the given boards.

If all boards have a side length of $1$ ~1~, then no moves can be made, so Mike wins.

If $N$ ~N~ is even, then we can show that Mike will win using the strategy stealing argument. First, group the boards into pairs. Then, whenever Nils makes a move on a board, Mike can make the same move on the other board in the pair. Thus, Mike will always be able to make a valid move, so he will win.

Otherwise, $N$ ~N~ must be odd, and we can show that Nils will win using the strategy stealing argument. First, Nils can move the nail in the first board to the top-left corner. Then, group the remaining $N-1$ ~N-1~ boards into pairs. When Mike makes a move, there are two cases:

Case 1: The move is made on the first board.

Since the nail was already in the top corner, then the move either decreased the length or width of the board. If Mike just decreased the length of the board by $X$ ~X~ units, then Nils can choose to decrease the width of the board by $X$ ~X~ units, and vice versa.
Case 2: The move is not made on the first board.

Then, Mike can perform the same move on the other board in the pair.

Hence, Nils will always be able to make a valid move, so he will win.

Note that this implies that Nils must win every game in subtask 1 unless $s_1 = 1$ ~s_1 = 1~, providing an $\mathcal{O}(1)$ ~\mathcal{O}(1)~ solution for subtask 1.

Time complexity: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

Subtask 3

For subtask 3, we will use dynamic programming to find the grundy number of each state. For the same definition of the state $(a, b, c, d)$ ~(a, b, c, d)~ as in subtask 1, we can define $dp[a][b][c][d] = mex\{S\}$ ~dp[a][b][c][d] = mex\{S\}~, where $S$ ~S~ represents the set of the grundy numbers of all states that our current state can transition to. The transitions are the same as the DP solution for subtask 1.

To check if adding a board allows Nils to win, we take the nim sum of the grundy numbers of each board, including the board that was added. If the nim sum is equal to $0$ ~0~, Mike wins. Otherwise, Mike loses.

Time complexity: $\mathcal{O}(\max(s_i)^5 + M)$ ~\mathcal{O}(\max(s_i)^5 + M)~

Subtask 4

For subtask 4, notice that we only require the grundy numbers of square boards with a nail on the bottom right corner, as they are the only boards that could appear and be added. Since we are only interested in $100$ ~100~ states, we can run our solution in subtask 3 to precompute these $100$ ~100~ values and store them in an array.

Any solution for subtask 3 with a reasonable constant factor should take less than 10 minutes for precomputation, and a well-implemented solution in C++ that makes use of the observation that the grundy numbers will remain small could even run in under one minute.

Time complexity: $\mathcal{O}(N + M)$ ~\mathcal{O}(N + M)~

Comments

4

Bungmint commented on Dec. 27, 2022, 8:01 a.m.

Oh wow, I actually did not think precomputing 100 grundy values would be the intended solution lol. It felt so wrong copy-pasting the 100 values after locally running the suboptimal solution. Anyways, interesting problem.

1

aaronhe07 commented on Dec. 27, 2022, 7:31 a.m. ← edited →

Subtask 1 can be solved with the following observation: if $n \ge 2$ ~n \ge 2~, player 1 always wins by moving the nail to the top left, then mirroring person 2's moves but in the other dimension, keeping it a square each time.

1

Josh commented on Dec. 27, 2022, 7:57 a.m.

Yeah, this is covered by the strategy in subtask 2.

0

aaronhe07 commented on Dec. 27, 2022, 6:47 p.m.

Oops, I should have read through it more.