FivePileSpecial
2020 TCO Final · 2020-11-12 · by misof
Problem Statement
Five Pile Special is a NIM variant: a two-player combinatorial game. It is played with five piles of tokens, arranged in a row.
There are three types of valid moves:
- The player selects one of the piles, selects a positive number x, and removes x tokens from the selected pile.
- The player selects three consecutive piles, selects a positive number x, and removes x tokens from each of the selected piles.
- The player selects all five piles, selects a positive number x, and removes x tokens from each of the selected piles.
The players take alternating turns. The player unable to make a valid move loses the game.
You are given a position in this game: the
Each move in this game can be represented as a sequence of five values: for each pile, the number of tokens removed from it. Find all winning moves for the given position and return their concatenation (in any order).
Notes
- An empty pile still counts as a pile. For example, if the token counts are {1, 0, 2, 3, 0}, the three non-empty piles are not consecutive.
- You may assume that for each position that matches the constraints given below there are at most 1,000 distinct winning moves.
Constraints
- piles will contain exactly 5 elements.
- Each element of piles will be between 0 and 10^18, inclusive.
{0, 0, 0, 7, 7}
Returns: { }
As most of the piles are empty, valid moves in this situation must only involve a single pile. Then, this is clearly a losing position: the second player can win by "mirroring" the first player's moves on the other pile.
{7, 7, 7, 7, 7}
Returns: {7, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 7, 7, 7, 7, 0, 0, 0, 7, 7, 7, 0, 0, 0, 7, 7, 7, 7, 7, 7, 7, 7 }
Taking 7 from all piles is a winning move: the opponent has no tokens left and loses immediately. Taking 7 from the first three piles is also a winning move: it produces the situation from Example 0. Further analysis can show that taking 7 from any other valid set of piles is also a winning move.
{47, 42, 0, 42, 47}
Returns: { }
A less trivial symmetric position that is losing for the same reason as in Example 0.
{10, 0, 11, 0, 12}
Returns: {3, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 11 }
We can emulate a traditional game of three-pile NIM.
{0, 11, 14, 19, 0}
Returns: {0, 0, 0, 14, 0, 0, 6, 6, 6, 0 }
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FivePileSpecial with a public method vector<long long> findWinningMoves(vector<long long> piles) · 107 test cases · 2 s / 256 MB per case