PigeonholeNim
TCO21 Round 4 · 2021-04-13 · by misof
Problem Statement
We have a wooden cabinet. The whole cabinet is divided into pigeonholes: a vertical grid of R rows times C columns of rectangular spaces that can contain objects.
Each pigeonhole contains some nonnegative number of tokens.
If a pigeonhole is empty, all pigeonholes that are higher in the same column are also empty.
You are given the numbers of tokens in the
Formally, if we number the rows 0 to R-1 top to bottom and the columns 0 to C-1 left to right, the number of tokens in cell (row r, column c) is piles[ R*c + r ].
We are going to play a version of the game of NIM with these pigeonholes. The rules are as follows:
- This is a two-player game. The players take alternating turns.
- Valid numbers are positive integers that do not contain the digits 4 and 7. (Some valid numbers are 1, 2, 3, 5, 6, 13, 290016, and so on. The numbers 0, 4, 7, 100402 and 2007407 are not valid.)
- A valid move consists of selecting a non-empty column and making one of two things:
- You may remove a valid number of tokens from the topmost non-empty pigeonhole in the chosen column.
- If a move of the first type would clear a pigeonhole completely and the column is not empty yet, you may also remove exactly one token from the pigeonhole immediately below the one you just cleared.
Note that you cannot remove tokens from more than two pigeonholes in the same turn. For example, suppose there is a column with three pigeonholes, containing 5, 1 and 7 tokens from top to bottom. If we select this column, we have the following ways to make a move:
- We may remove 1, 2, 3, or 5 tokens from the top pigeonhole.
- We may remove 5 tokens from the top and 1 from the middle pigeonhole.
Note that removing 5 from the top, 1 from the middle and also 1 from the bottom is not a valid move: even if we clear the second pigeonhole along with the first, that's all we are allowed to do.
The game ends as soon as any one column becomes empty, even if there are still tokens in other columns.
There are two ways in which the winner can be determined:
- If emptyWins = 1, whoever created the empty column wins.
- If emptyWins = 0, whoever created (or, most likely and more precisely, whoever was forced to create) the empty column loses.
You are given the initial position of the game, as described above, and the value of emptyWins. It's your turn. Return the number of distinct winning moves you have in the given position.
Notes
- We are using the standard meaning of "winning moves": A move is a winning move if after making the move you will have a strategy that guarantees that you can win the game regardless of how your opponent plays.
- Two moves are distinct if they affect different columns, and also if they affect the same column and leave it in a different state.
Constraints
- R will be between 1 and 20, inclusive.
- C will be between 1 and 20, inclusive.
- piles will have R*C elements.
- Each element of piles will be between 0 and 200, inclusive.
- Each column in the grid of pigeonholes will be non-empty.
- In each column, if a pigeonhole is empty, all pigeonholes that are higher in the same column are also empty.
- emptyWins will be either 0 or 1.
1
1
{9}
1
Returns: 2
We can win simply by taking all 9 tokens from the only pigeonhole, as this creates an empty column. We can also win by taking 5 tokens. This leaves our opponent with 4 tokens, and they cannot take all of them. After their move we can take the rest.
1
1
{17}
0
Returns: 2
Here we want to force our opponent to clear the only column. The most straightforward way of doing so is by taking 16 tokens, but we can also take just 12, leaving the opponent with 5 tokens.
4
1
{121, 1, 1, 123}
1
Returns: 2
There is one column: +------+ | 121 | +------+ | 1 | +------+ | 1 | +------+ | 123 | +------+ Making a move of the second type wins us the game. (We take the 121+1 tokens from the top two pigeonholes. Our opponent can then either just take 1 token from the third pigeonhole, or 1+1 from the fourth. In either case, we can take all that remains in our next turn.) Perhaps surprisingly, taking 80 tokens from the top pile is also a winning move.
2
4
{2, 19, 2, 191, 2, 111, 2, 33}
1
Returns: 0
This is a losing position. If our opponent is smart, we will eventually be forced to clear a cell in the topmost row, and once that happens, our opponent will clear the rest of the column. (Note that we cannot save ourselves by doing a move of the second type.)
2
4
{2, 19, 2, 5, 2, 111, 2, 33}
1
Returns: 1
This seems to be a similar situation to the one in the previous example. However, now the bottom pigeonhole in the second column only contains 5 tokens. This changes the game quite significantly. There is exactly one winning move: to remove one token from the top pigeonhole in that column (turning it from {2,5} to {1,5} ). In this situation, there are exactly four independent moves that don't immediately lose the game: removing one token from one of the other columns, or removing 1+1 tokens from column 2 (leaving four tokens in the bottom pigeonhole). Our opponent will play the first of these moves, we play the second, they play the third, we play the fourth. (The order does not matter. If they do anything else, they lose.) Now we have columns {1, 19}, {0, 4}, {1, 111}, and {1, 33}. Regardless of what our opponent does next, we can win in our next turn.
3
3
{1, 1, 1, 1, 1, 1, 1, 1, 1}
0
Returns: 3
Nobody wants to be the one who empties a column and loses. The three winning moves we have in this position are as follows: choose any column and remove 1+1 tokens from it.
5
3
{0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1}
0
Returns: 3
The same example as the previous one but now with two empty pigeonholes on the top of each column. These don't change anything, the three winning moves remain the same.
3
4
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
1
Returns: 3
+---+---+---+---+ | 0| 3| 6| 9| +---+---+---+---+ | 1| 4| 7| 10| +---+---+---+---+ | 2| 5| 8| 11| +---+---+---+---+
Submissions are judged against all 90 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PigeonholeNim with a public method int countWinningMoves(int R, int C, vector<int> piles, int emptyWins) · 90 test cases · 2 s / 256 MB per case