Permutation game Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Permutation game
You are viewing a single comment's thread. Return to all 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.