Can someone please help me with this problem ( https://www.codechef.com/COOK94B/problems/CHEFLAKE )? I am not able to understand the DP approach (mentioned in the editorial) behind this problem. @vijju123
Thanks.
It is my job to convert answers there into questions if they pass the discuss standards. 
1 Like
@l_returns, I mentioned in the question that I am not able to understand the approach mentioned in the editorial. Can you please explain it in a simple way?
I didn’t had solved that during or after contest though I participated in that contest… Let me try to understand the soln… I ll get back to u once I understand it…
I can attempt to explain what I understood from the editorial.
Let’s call the two parties A and B for convenience. A starts at (1,1) and goes to (1,M). B starts at (N,1) and goes to (N,M). Notice that both must take the same number of steps to the right in their journey. These steps increment the column they are at, in other words these steps are of the form (r,c) \rightarrow (r,c+1).
So let’s say they decide to make each of these right steps together. Then the journey can be broken into several “stages”. A stage starts with A at (i', c-1) and B at (j', c-1). Then they both step into the next column together. A reaches (i',c) and B reaches (j',c). Then A moves a certain number of steps up or down, as long as the steps are valid, to reach (i,c). Similarly B moves to (j, c). They will take exactly M such stages to reach the column M from column 0. If A ends up at (1,M) and B at (N,M), then that is a valid end condition.
By introducing the concept of stages, have we imposed any restrictions on the original problem?
The answer is no. The problem is unchanged but the stages will be helpful in formulating the solution.
Let’s say f(c,i,j) is the number of ways A and B can end up on (c,i) and (c,j) respectively after completion of a stage. Now if you think in reverse, A comes to (i,c) from (i',c). But i' can only belong to some continuous segment [L_A..R_A]. This segment [L_A ..R_A] is the largest segment that includes i, does not include j, and does not include any rocks. There exists a similar valid segment [L_B..R_B] for j'. Note that L_A, R_A, L_B, R_B are different for each state, thus they depend on c, i, j.
For each valid pair (i',j'), f(c-1,i',j') contributes to f(c,i,j). Thus, we can define
f(c,i,j) = \sum_{i'=L_A}^{R_A} \sum_{j'=L_B}^{R_B} f(c-1,i',j')
This is a 3 dimensional dp. The calculation of each state can take \mathcal{O}(N^2), so overall complexity is \mathcal{O}(N^4 M). However, the calculation of each state can be optimized.
L_A, R_A, L_B, R_B can be calculated in constant time with some preprocessing on the grid that stores the closest rock above and below a cell for each cell. And due to this particular form of dp transition, a 2D prefix sum table built on the dp table f(c-1, *, *) can be used to make the sum queries over a rectangular range in constant time to get any f(c, i, j).
Now complexity is \mathcal{O}(N^2M).
I found the tester’s solution helpful: link. And here is my own: 18642831.
@meooow, Can you please tell me how are you calculating the prefix sums in your code ? I don’t understand these two lines:-
1)pre[i][j] = (dp[i][j] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1])
2)dp[i][j] = pre[RA][RB] + pre[LA - 1][LB - 1] - pre[RA][LB - 1] - pre[LA - 1][RB]
I am posting this as an answer as I can’t comment on your answer. Thanks.
Thanks for your answer. I just have one small doubt. Is it necessary for (LA,RA) and (LB,RB) to be non overlapping ? If LA = 1, RA = 5, LB = 2, RB = 7, i=2, j=8, then we might count cases where A can move from 5(of previous stage) to 2(of current stage) and B can move from 2(of previous stage) to 8(of current stage) which causes both of them to intersect at a point ?
First of all, minor problem in your example: [L_B..R_B] must contain j and not contain i. But I understand your question.
The paths of A and B are not allowed to intersect. So a situation where one cell on path of A is directly below one cell on path of B is impossible because it means their paths do intersect. This means f(c,i,j) = 0 for i \ge j.
So in case [L_A..R_A] and [L_B..R_B] intersect, it is not a problem because for i' \ge j' the stored dp value f(c-1, i', j') will be 0 and will have no effect on the sum.
In your example, f(c-1, 5, 2) will be 0.
@rajesh_xyz pre is the 2D prefix sum table which is built on dp table. The working is well explained here, hope it helps