You are not logged in. Please login at www.codechef.com to post your questions!

×

MATTEG - Editorial

8
1

Problem Link

Practice
Contest

Author: Alexandru Valeanu
Tester: Hasan Jaddouh
Editorialist: Bhuvnesh Jain

Difficulty

MEDIUM

Prerequisites

Recursion, Bitmask Dynamic Programming, Hashing

Problem

You are given a grid, $R*C$, where each location has some number written on it. You are also given $N$ teleportation pairs (dx, dy), meaning that you can go from $(a, b)$ to $(e, f)$ iff $|a-e| = dx$ and $|b-f| = dy$, where $|x|$ denotes the absolute value of $x$. You are required to find a sequence of steps so that you use as maximum number of teleportation pairs (atmost $N$), each one only once, and try to maximise the sum of the number on the locations you visited.

Quick Explanation

Since, we need to use each teleportation pair once, we can store a bitmask where the set bits denotes which what teleportation pairs are still not used up. Then we can simply iterate over the possible next states based on the current location and bitmask and use dynamic programming to solve the above problem. Since, the number of locations that might be visited are limited, try to optimise the dynamic programming solution using hashing to handle the case of excess memory usage.

Explanation

Subtask - 1

No dynmaic programming or any advanced techniques are required to solve this subtask. Only simple recursion which traverses all the possible positions depending on the remaining teleportation pairs is enough. But this solution is quite slow to pass other subtasks.

Subtask - 2

We can simply see that subproblems of many recursive calls of above solution are overlapping. To clearing differentiaite between the different states, we create an dynamic programming array consisiting of 3 states, namely the current x-coordinate, current y-coordinate and the mask denoting the teleportation pairs still to be used. Thus our dynamic programming array looks like $dp[x][y][mask]$.

Building the above the dynamic programming bottom up, would lead to complexity of $O(R*C*N*{2}^{N})$, which is quite slow for final 2 subtasks. Also, the memory used by the above approach will be of the order of $O(R*C*{2}^{N})$, which would cause memory limit issues with last 2 subtasks as well.

Subtask - 3

In the above approach it is easy to see that most of the states would be unreachable. For example, there might not exist any sequence of steps (of length <= $N$), such that we can reach from $(a, b)$ to $(c, d)$. Also, there might be cases we could reach from $(a, b)$ to $(c, d)$ only through particular sequence of moves, meaning that all "mask" positions might not be visited also. Thus, we need to avoid these redundant calculations in the above approach and also try to find an more strict upper-bound on the number of visited states in the above dynmaic programming solution.

Let us first define what a valid teleportation is. A teleporation is said to be valid if from a location on a grid, we can go to a location present on the grid. It is invalid, if we go to a location outside the grid.

We try to find a tighter upperbound for the number of states visited. Now, let us say, we are at a particular location, $(a, b)$, then we have 5 possible choices to take from the current location, i.e. either stay in the current location (since we can't use any valid teleporation) or jump in any of the 4 directions (if jump is valid i.e. inside the grid). Also, at each steps, we would have to choose from $K$ of the remaining teleportation pairs to go to next point. Thus, we can say that we have an upperbound of $O(min(N*{5}^{N}, R*C*N*2^{N}))$ on the number of states that are visited. (Why minimum is taken is because, we either visit all the states in which case the bound is simply $R*C*N*{2}^{N}$ or we can't take some valid teleportation pair at some location and visit less states, leading to $N*{5}^{N}$ bound).

Now, let us try to write the above solution in top-down appraoch i.e. using recursion with memoisation. This, will lead us to visiting only those states which are reachable from starting state i.e $dp[Sx][Sy][{2}^{N}-1]$. Thus, in recursive solution for subtask - 1, we simply add the dynamic programming approach. But there is still a catch here i.e the memory requirement. The memory required by this solution is still $O(R*C*{2}^{N})$, which limits us from passing this subtask. But our time complexity of the solution has decreased. To get a trade of between the time and space complexity, we can use "maps" or "unordered maps" to store the list of possible "masks" or "locations" as per implementation. This will increase the time complexity by logarithmic factor, but the space complexity would now be order of the number of possible states. Using this optimisation, we can easily pass the given subtask.

Subtask - 4

We are almost close to the full solution now. We just need to lower the trade off we did between memory and time in the last approach. For this, we will use hashing approach, to remove the logarithmic factor from the above last approach. (It may seem that unordered_map would suffice for this subtask too, but since they number of states in the unordered map are large, rehash would be called many times, which is a costly operation and lead to the solution becoming slower).

First let us consider mapping 3 states into a single number without any collision at all. Since, $(a, b)$ are grid points, we can represent each grid point into a single integer as $a * C + b$. Thus now, the states reduce to $2$. We can again apply similar operation to reduce the states to $1$. For example mapping $(a, b, mask)$ to single integer $(a * C + b) * {2}^{N} + mask$. The order of this number is $O(R*C*{2}^{N})$. We can simply hash this number to another value, i.e. build a hash table for these values. Suppose, we have successfully build our hash table, then we can easily see that we can retrieve the elements in $O(1)$, thus removing the logarithmic factor from above solution. Care must be taken while choosing the size of hash table. Taking it too small would be of no use due to large number of collisions. We should chose the size around the number of states that can be reached, thus reducing the number of collisions while inserting the keys into it. Also, we can either implement hashing using linear probing or separate chaining. The author chose linear-probing to implement the hashing technique.

For more details, you can refer to the author's solution below.

Tester's Solution for full problem

The tester's solution used the fact that we have $5$ choices at each and every point on the grid. Thus similar to bitmask where we have $2$ bits to represent a states, he represented each states used base $5$ encoding where $0$ means we stay at the same location, and $1$ to $4$ means we chose one of the 4 directions. Simliar to iterative bitmasking solution which are written traversing each mask from $0$ to $2^N - 1$, the solution traverse each base $5$ mask from $0$ to $5^N - 1$. Then based on the values in the mask, we just perform the teleportation and check whether we land at valid grid point or not. If yes, we update the answer for that mask. The final answer is the maximum over all the mask values calculated. The time complexity of this solution is exactly $N * 5^N$, and it doesn't use any hashing. Also, the 2 dimensions where we store the current $x$ and $y$ coordinate in above solution is not required here as it is captured in the base case, where we store the cost of starting point.

For more details, you can refer to tester's solution below.

Time Complexity

$O(min(N*{5}^N, R*C*N*{2}^{N}))$

Space Complexity

Size of Hash Table ~ $O(min({5}^N, R*C*{2}^{N}))$

Solution Links

Setter's solution
Tester's solution
Editorialist solution - For 70 points, (No implementation of hash table)

This question is marked "community wiki".

asked 24 Aug '17, 16:11

likecs's gravatar image

6★likecs
3.7k2380
accept rate: 9%

edited 01 Sep '17, 05:05


I used brute force to check all cases, and terminated the search if we went outside of the grid, or it was sure if we can't get better sum than our previously found best. (Added the max value in the grid to the current sum x times, where x is the number of not used tel-pairs)

I got 100 points for this approach, which quite surprised me, because it's possible that these terminations don't occour oftenly enough, and then the complexity is $O(4^N*N!*T) = O(4^9*9*5) = 4.75*10^{11}$.

Maybe the tests aren't strong enough.

link

answered 26 Aug '17, 23:13

bazsi700's gravatar image

6★bazsi700
3979
accept rate: 11%

edited 26 Aug '17, 23:15

2

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).

(26 Aug '17, 23:15) alexvaleanu4★

@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.

(26 Aug '17, 23:39) bazsi7006★
2

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).

(26 Aug '17, 23:41) alexvaleanu4★

The practice link is incorrect.

link

answered 26 Aug '17, 23:14

code2222's gravatar image

1★code2222
1
accept rate: 0%

Updated. :)

(26 Aug '17, 23:21) likecs6★

Can anybody tell me why my brute force solution gives WA for test case 1? Link

link

answered 26 Aug '17, 23:26

ps_1234's gravatar image

4★ps_1234
593
accept rate: 0%

Please help!

(27 Aug '17, 01:36) ps_12344★

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.

(27 Aug '17, 02:02) likecs6★

damn,thank you!

(27 Aug '17, 02:04) ps_12344★

Submissions https://www.codechef.com/viewsolution/15132023 and https://www.codechef.com/viewsolution/15125137 are identical, still the later gave a WA during the contest which led to a penalty. Please check the issue.

link

answered 26 Aug '17, 23:34

amandeep224's gravatar image

4★amandeep224
01
accept rate: 0%

No penalty in lunchtime :)

(26 Aug '17, 23:35) vijju123 ♦♦5★

I can't see a WA associated with the faulty submission.

(26 Aug '17, 23:37) alexvaleanu4★

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.

(27 Aug '17, 02:25) amandeep2244★

can anyone please explain how this (N * (5 ^N)) comes and hoe it reduces the dp states (how does skipping some possible position leads to correct answer) ?

link

answered 27 Aug '17, 07:56

pk301's gravatar image

2★pk301
62710
accept rate: 16%

@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.

(27 Aug '17, 09:58) likecs6★

sorry but i didn't understand the third subtask part ..can u please explain a little more !

(27 Aug '17, 12:01) pk3012★

$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.

(27 Aug '17, 20:34) likecs6★

@likecs can you please provide a link from where i can understand that it's covering all the possible permutations ! As far i understand i think that i land on (5^n * 2^n) solution

(12 Sep '17, 19:21) pk3012★

According to the editorial at each step we have 5 choices to move and k choices to choose from the available teleportation pairs so at each step the shouldn't the number of possible ways to move equal to 5k . Since there are n steps the total no of ways should be (5k)^n where k<=n . So this must be equivalent to (5n)^n instead of n*(5^n).Correct me where i am wrong.

link

answered 27 Aug '17, 12:58

utkarshg_1998's gravatar image

4★utkarshg_1998
232
accept rate: 0%

edited 27 Aug '17, 13:00

@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.

(27 Aug '17, 20:31) likecs6★

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.

(27 Aug '17, 20:31) likecs6★

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 :)

link

answered 27 Aug '17, 23:12

venture_walk's gravatar image

4★venture_walk
11
accept rate: 0%

edited 27 Aug '17, 23:13

@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.

(28 Aug '17, 02:58) likecs6★

Thank you so much for replying.

And what was the significance of multiplying with 2^N in (a∗R+b)∗2^N+mask, again? :sweat_smile:

(28 Aug '17, 09:49) venture_walk4★

And I also came to know that boost::unordered_map is slower than std::unordered_map. :/

(28 Aug '17, 09:50) venture_walk4★

@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.

(28 Aug '17, 10:36) alexvaleanu4★

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 :)

(28 Aug '17, 11:03) venture_walk4★

Exactly!

You're welcome!

(28 Aug '17, 12:06) alexvaleanu4★
showing 5 of 6 show all

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?

https://www.codechef.com/viewplaintext/15129394

link

answered 28 Aug '17, 18:03

sahil_k's gravatar image

4★sahil_k
1
accept rate: 0%

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.

link

answered 30 Aug '17, 13:41

hrushikesh_t's gravatar image

4★hrushikesh_t
534
accept rate: 0%

edited 30 Aug '17, 13:42

@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.

(30 Aug '17, 15:38) likecs6★

@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.

link

answered 30 Aug '17, 21:15

givingmybest's gravatar image

4★givingmybest
1014
accept rate: 28%

@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.

(31 Aug '17, 04:20) likecs6★

@kingofnumbers

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

link

answered 30 Aug '17, 23:53

taran_1407's gravatar image

6★taran_1407
3.9k2895
accept rate: 22%

edited 02 Sep '17, 23:53

@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.

(08 Sep '17, 03:56) likecs6★

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.

(08 Sep '17, 03:57) likecs6★

In case of further doubt's you can ask again. :)

(08 Sep '17, 03:57) likecs6★

Tester's solution link isn't working Nor editorialist's...

(08 Sep '17, 11:45) taran_14076★

check these:

tester : https://ideone.com/csfZJZ

editorialist : https://ideone.com/k6PWH8

(08 Sep '17, 11:53) likecs6★

Thanks for all this support.. :) @likecs

By the way, i am learning to use dp+bitmask to account for permutations.. (which is an entirely new territory to me).

Anyway, Thanks

(09 Sep '17, 18:53) taran_14076★
showing 5 of 6 show all

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;
link
This answer is marked "community wiki".

answered 31 Aug '17, 03:28

john_smith_3's gravatar image

6★john_smith_3
59517
accept rate: 26%

@john_smith_3, yes your observation is correct. The solution will be updated soon as well as the editorial. Thanks for pointing it out.

(31 Aug '17, 04:22) likecs6★

@john_smith_3 You are right! Thanks for finding the bug!

(31 Aug '17, 11:12) alexvaleanu4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,683
×2,595
×2,172
×145
×64
×17

question asked: 24 Aug '17, 16:11

question was seen: 2,623 times

last updated: 12 Sep '17, 19:21