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.
5^N basically comes from the fact that at each location, we have 5 choices to go with i.e stay at same location or go to one of the 4 possible directions. I recommend you to write solution for 40 points and print the {x, y, mask} tuples visited in recursion and check that all states are not being visited. For help, you can see author or mine code with the debugging statement removed. I hope this makes it more clear.
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 
@venture_walk, yes it is necessary as explained in the editorial regarding shortcomings of map and unordered_map. This is not required if you solve using tester’s approach as x & y coordinate are not required to be stored now and it will easily fit in memory. Also remember, using large memory in program also increases runtime as well as cache effects reduce.
Thank you so much for replying.
And what was the significance of multiplying with 2^N in (a∗R+b)∗2^N+mask, again? 
And I also came to know that boost::unordered_map is slower than std::unordered_map. 
@venture_walk It was an encoding of the state in the dp. The state is (x, y, mask) where x and y are the coordinates of the cell and mask is the configuration of tel-pairs. Now, we can uniquely identify (x, y) as a single value, x * (N - 1) + y. This is a value that uses 20 bits. If we shift it by N bits then we can store the mask as the last N bits.
It is equivalent to storing tuples (x, y, mask) but much faster.
boost::something is usually better than std::something but boost is not allowed in online judges.
Oh! I see the awesomeness : “If we shift it by N bits then we can store the mask as the last N bits.”
Thank you so much
Exactly!
You’re welcome!
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.
@hrushikesh_t, you are not clearing the dp for every test case. Also, this solution will still tle as you are using unordered_map. See editorial for more details. You need to implement your own hash table or else use tester’s approach.
@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;@givingmybest,changing from 0->2^N-1 to 2^n-1->0 doesn’t make any difference. Also, in general contests, you will not get memory limit as 2GB. So, it is preferred you learn new techniques here. It may be possible that with such large memory, cache effects play major role and switching parameters like [x][y] to [y][x] may lead to different running times on same test cases and will depend on test cases as well. So, I would recommend to avoid this solution.
@john_smith_3, yes your observation is correct. The solution will be updated soon as well as the editorial. Thanks for pointing it out.
@taran_1407, I would first advise you to read about travelling salesamn problem solution using bitmasking. The idea is similar here. The mask (base 5) contains the best possible solution inside it considering all permutations. When adding a new teleportation pair into current mask, we just need to check whether it will lead to valid move or not and add the node value (if move is valid) to the value stored in mask.
For this also, I suggest you to first try to write recursive solution, where you will see the permutation you are talking about is clearly taken care of. Then, you may read and understand the tester’s solution.