What is the significance of multiplying with 2^N in (a∗R+b)∗2^N+mask?
I tried multiple approaches with and without unordered_map, nested unordered_map, multiplying with 2^N(as mentioned), reserving memory in advance, changing the max_load_factor and what not but nothing seems to work.
I always get a TLE on Task#3 of Subtask#4.
Is it really that necessary to implement a custom hash table. Some insights are really appreciated.
I wrote a simple recursion for the first subtask in Python 2.7, and it’s working for all the given test cases, but is giving WA when I submit. Amy boundary conditions or logic gaps that I’m missing in my code?
Can someone please point out the error in my solution?
I submitted first solution, using @likecs 's idea, without hashing and got 70 points. Then, I tried the solution using hashing which fails at 3-4 test cases.
@likecs I didn’t get how using DP from “0 => (2^N-1)” to “(2^N-1) => 0” changes the time complexity. Can you provide some resources for reading about it. Also I don’t get why dp[R][C][2^N-1] will be a trouble. It can be made easily as we need only ints and max 2GB space will be taken up. Help would be appreciated.
I know! I have seen your solution during the contest. You are not the only one you managed you get full points by using this idea. First of all, congratulations! I didn’t think of this idea!
Also, I would like to apologize to all contestants who got full marks using the ‘right’ solution(s).
@alexvalenau Will there be more test cases in practice? I feel a little guilty after seeing the much harder solution here, and knowing my solution could be easily countered by some test cases.
Hi, it seems you read the input wrong. It was stated that we fisrt give all the x coordinates and then all the y coordinates. But you are reading numbers in pairs. Rest seems fine to me.
Yeah, it isn’t showing there.Its not showing an AC/TLE/RTE eihter. But I can see the WA on my submissions list. Maybe thats why it was judged wrongly. Please have a check.
@pk301, can we clarify a bit more. Also, we are not skipping any possible states. All the required states (which will lead to answer) are captured into the solution.
@utkarshg_1998, yes by first intuition , your approach looks correct. But think in terms of masking. For example, when writing Travelling salesman problem solution, you see that that each point you have k edges to chose from at a vertex. but still the complexity is not like you mentioned. n * 5^n, signifies that first states would capture which one was chosen and the next which possible directions.
I think it will be more clear from tester’s solution his approach is totally based on this. From his code it will be clear that all possible states are being visited from it. I hope it make things somewhat more clear.