Connection Status:
Competition Arena > YetAnotherTokenGame

YetAnotherTokenGame

TCO19 Round 2A · 2019-04-15 · by misof

TCO19 Round 2A · 2019-04-15 · by misof · Dynamic Programming
Class Name: YetAnotherTokenGame
Return Type: String
Method Name: getWinner
Arg Types: (vector<int>)
Problem Statement

Problem Statement

William and Xenia are fans of NIM-style games. Today, they came up with a new variant and they are both really excited to play it.

As is usually the case, the game is played with some piles of tokens, the players take alternating turns, and the person who is unable to make a valid move loses the game.

In this version of the game, the valid moves look as follows: The current player announces either "take" or "split". Then:

  • If they chose "take", they must choose one non-empty pile of tokens and remove one or more tokens from the pile.
  • If they chose "split", they must choose a pile with at least two tokens and split the chosen pile into two or more smaller piles.

For example, if there is a single pile with 7 tokens, the current player has multiple possibilities for a valid move, including these:

  • Announce "take" and remove three tokens, leaving a single pile with four tokens.
  • Announce "take" and remove all seven tokens, leaving an empty pile.
  • Announce "split" and split the pile into a pile with two tokens and a pile with five tokens.
  • Announce "split" and split the pile into seven piles containing one token each.

You are given the int[] piles. Consider the position of the game where William is the next player to move, and the elements of piles are the sizes of the piles of tokens. Determine and return the winner of the game, assuming both players play optimally.

Constraints

  • piles will contain between 1 and 50 elements, inclusive.
  • Each element of piles will be between 1 and 300, inclusive.
Examples
0)
{47}
Returns: "William"

William can take all tokens and win in a single turn. (More precisely, after William takes all tokens, Xenia will be unable to make a valid move.)

1)
{1,1,1,1,1}
Returns: "William"

The only valid move in this situation is choose "take" and to remove one of the tokens. Eventually, William will remove the last token and then Xenia will lose the game.

2)
{3,1,1,1}
Returns: "William"

One winning move for William is to remove two tokens from the pile with three tokens. Another winning move is to split this pile into three piles, each containing one token.

3)
{3,42,47,3,42,47}
Returns: "Xenia"

This position is symmetric. Xenia can use this symmetry to copy William's moves, and if she does that, she will eventually win the game.

4)
{300,42,47,3,42,47}
Returns: "William"

One winning strategy for William is to produce the configuration from Example #3 and then to follow Xenia's strategy from that example.

Submissions are judged against all 115 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class YetAnotherTokenGame with a public method string getWinner(vector<int> piles) · 115 test cases · 2 s / 256 MB per case

Submitting as anonymous