TopCoder problem "NimForK" used in SRM 419 (Division I Level Two)



Problem Statement

    

The game of NimForK is played as follows. There are k players sitting in a circle numbered 1 through k in clockwise order. Starting with player 1, the players take turns making moves in clockwise order. In the center of the circle, there is a pile that initially contains n stones.

When a player takes a turn, he must remove some number of stones from the pile. The number of stones he is allowed to take is dependent on the size of the pile. You are given a String[] moves, where the i-th element (1-indexed) is a space separated list of the number of stones that can be removed when the pile contains i stones. For example, if there are currently 3 stones in the pile, and moves[3] is "1 3", then the player can remove either 1 stone or 3 stones from the pile. The player who takes the last stone wins.

Each player uses the following strategy to determine how many stones he will remove during his turn:

  • If there is a move that ensures he will win regardless of how the other players move for the rest of the game, he will make that move. If there are several such moves, he will randomly choose one of them with equal probability. In other words, pretend that the other players are not following the strategy described here, and that it's possible for them to make any valid moves during their turns. If there is a move that will guarantee him to win in that scenario, he will make that move.
  • If there is no such move, then assuming that the other players are following this same strategy, he will make a move that gives him a non-zero chance of winning. If there are several such moves, he will randomly choose one of them with equal probability.
  • If neither of the above moves are possible, he will randomly choose any valid move with equal probability.

If there are no valid moves possible during a player's turn, but there are still stones left in the pile, the game ends and nobody wins.

Return a int[] containing all the players who have a non-zero chance of winning the game. The int[] must be sorted in ascending order.

 

Definition

    
Class:NimForK
Method:winners
Parameters:int, int, String[]
Returns:int[]
Method signature:int[] winners(int n, int k, String[] moves)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 50, inclusive.
-k will be between 2 and 20, inclusive.
-moves will contain exactly n elements.
-Each element of moves will have length between 0 and 50, inclusive.
-Each element of moves will contain a space separated list of integers.
-Each integer in moves[i] will be between 1 and i + 1, inclusive.
-All integers in moves[i] will be distinct.
 

Examples

0)
    
8
2
{"1", "1 2", "1 2 3", "1 2 3", "1 2 3", "1 2 3", "1 2 3", "1 2 3"}
Returns: {2 }
This is a standard variation of nim where each player is allowed to take 1, 2 or 3 stones. In a game for two players the first player wins if and only if the number of stones in the initial pile is not divisible by 4.
1)
    
7
2
{"1", "1 2", "1 2 3", "1 2 3", "1 2 3", "1 2 3", "1 2 3"}
Returns: {1 }
Same as the previous example. Here 7 is not divisible by 4, so the first player wins.
2)
    
5
3
{"1", "1 2", "1 2 3", "1 2 3", "1 2 3"}
Returns: {2, 3 }
When there are three players and five stones, the first player cannot win. However, he decides who would win by taking either 1 stone (in this case the third player would win) or 2 or 3 stones (in this case the second player would win).
3)
    
6
3
{"1", "1 2", "1 2 3", "1 2 3", "1 2 3", "1 2 3"}
Returns: {1, 3 }
Here the first player cannot force his victory. His options are: take 1 stone - in this case the second player would decide whether the third player, or the first player would win (see previous example); take 2 stones - in this case the third player would win; take 3 stones - in this case the second player would win. He chooses the first option because in this case he can win with non-zero probability.
4)
    
1
20
{""}
Returns: { }
A delicate case. No player can make a move, so nobody can take the last stone. Therefore nobody can win.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10085

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13510&pm=10085

Writer:

andrewzta

Testers:

PabloGilberto , Olexiy , marek.cygan , ivan_metelsky

Problem categories:

Search