I was trying to understand the solution to this problem. But I don’t think that I have really got the solution to get full score, also I don’t think I have got something from this, I don’t feel confident apply the same idea to other problems.
Here are some of my doubts about the solution:
- first of all I don’t understand the “it seems natural” here: “Notice that, no matter how we define the DP state, these two complexities will always multiply to O(M). Therefore, we want to find a restriction such that both complexities are O(\sqrt{M}). This motivates using a blend of dp1 and dp2. Since dp12 already restricts bits, it seems natural to consider applying dp1 on some bits of x and dp2 on the rest.” what is the thought process here?
- I’m not sure I got the idea behind choosing dp[i][j][k]. (I’ve understood why that is correct but I wouldn’t be able to apply it again), is this correct: dp[i][j][k] is the maximum value for all numbers that have i as the first 10 bits and that have k bits in common with j in the last 10 bits, also in this dp we actually dropped a dimension and that is the index we are currently, right?
- last thing, shouldn’t this problem be put in the meet in the middle section?
- are there other way to solve this problem in O(N\sqrt{M} ? Originally I thought about splitting the number x in two parts but I didn’t think about using dp2 so I was stuck.