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.
PS: Nice question.
Thank You 
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.
Link 1: Without hashing. Gets 70 points.
Link 2: With hashing. Fails on 3-4 tests.
@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.
Can anyone explain me how does the tester’s solution account for different permutations of teleportation that may be applied.
Please Clarify.
PS: i thought of the same approach as tester’s but failed to account for permutations of teleportation used.
Thanks in advance
I suspect a bug in the setters solution.
I tried running the setters solution on this test case:
1
3 5 2
1 2
1 0
2 1
1 1 1 2 1
1 1 3 1 1
4 5 1 1 1
The correct answer should be 12 (given by 3 + 4 + 5), but I actually get the answer 9.
The line
auto code = ((x * (R - 1) + y) << 10) ^ mask;
should read
auto code = ((x * C + y) << 10) ^ mask;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).
Updated.
No penalty in lunchtime
I can’t see a WA associated with the faulty submission.
@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.
I will add some tomorrow. You should not get 100p after that!
You don’t have to feel guilty! I would have done the same (and I am sure I am not the only one).
Please help!
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.
damn,thank you!
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.
sorry but i didn’t understand the third subtask part …can u please explain a little more !
@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.