- Prepare
- Algorithms
- Game Theory
- Permutation game
- Discussions

# Permutation game

# Permutation game

+ 2 comments used bitmasking dp. n <= 15, so integer mask can be used to represent remaining set of numbers of given permutation. Create array dp[] of size pow(2, 15). dp[mask] is zero if the set represented by mask is an increasing sequence. i.e it is a loosing position. dp[mask] is one otherwise. (winning position).

To solve for a given

`mask`

, check for the sequence it forms whether its an increasing sequence, if it is we know the player given this`mask`

can not make a move, hence dp[mask] can be set to 0. Else, solve for each`new mask`

which can be made from given`mask`

by removing a single number from sequence represented by our`mask`

. if any generated`new mask`

is a loosing position, we can say our`mask`

represents a winning position, else it represents a loosing postion.

+ 0 comments Please put up the editorial for this problem!!!

+ 1 comment i cannot get the logic of how in 5 3 2 1 4 bob win the match ,,,,actually 1.alice will remove 5 2.bob will remove 3 3.alice will remove 2 after now the sequences is alredy in incresing order...plz any one tell wt's wrong with that ...

+ 0 comments I found these two 15-point "easy" problems by Shafaet an excellent introduction to this one: https://www.hackerrank.com/challenges/a-chessboard-game-1 https://www.hackerrank.com/challenges/game-of-stones-1 I was able to use the same logic I used in those to solve this one. (Recursion, and a hash storing results so far to avoid redundancy.)

+ 1 comment For anyone getting timeout, make sure to use bitmasking instead of data structures to maintain state.

Sort 30 Discussions, By:

Please Login in order to post a comment