- 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 thismask
can not make a move, hence dp[mask] can be set to 0. Else, solve for eachnew mask
which can be made from givenmask
by removing a single number from sequence represented by ourmask
. if any generatednew mask
is a loosing position, we can say ourmask
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