Sort 30 Discussions, By:
Please Login in order to post a comment
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.
Please put up the editorial for this problem!!!
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 ...
I found these two 15-point "easy" problems by Shafaet an excellent introduction to this one:
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.)
For anyone getting timeout, make sure to use bitmasking instead of data structures to maintain state.