I recently read somewhere that some DP solutions like knapsack can be optimised and the overall complexity can be reduced by a factor of 32 using std::bitset in C++.
Can someone explain this optimisation and the kinds of DP on which this works ?
I recently read somewhere that some DP solutions like knapsack can be optimised and the overall complexity can be reduced by a factor of 32 using std::bitset in C++.
Can someone explain this optimisation and the kinds of DP on which this works ?
Problem Link.
I've seen the public solutions but I am unable to understand them.
This is a game theory problem with Grundy Numbers but I am unable to break this game into smaller independent games in order to apply the Grundy theorem.
Can somebody please provide the solution with explanation ?