PROBLEM LINK:Author: Sunny Agarwal DIFFICULTY:Simple PREREQUISITES:Greedy, dynamic programming PROBLEM:There are two lanes $L_1$ and $L_2$, each containing $N$ blocks, and $L_1$ is on top of $L_2$. Chef starts running from the beginning of (any) one of the lanes and must reach the end of any lane. To do so, Chef can use the following jumps (assuming he's currently at the $x$th block of some lane):
Some of the blocks are dirty, which means Chef cannot step over them. You need to know whether Chef can reach the end and if so, what is the minimum number of gravity switches necessary. QUICK EXPLANATION:The second kind of jump is not helpful, so we only use the first and third. It's also not helpful to switch lanes unless there is an obstacle to avoid. With this in mind, there is one obvious optimal path that we should consider (i.e. switch lanes only if necessary):
There's also a dynamic programming approach: let $D_1(x)$ and $D_2(x)$ be the fastest way to reach the $x$th block of lanes $L_1$ and $L_2$, respectively. Then:
We define $D_1(0) = D_2(0) = 0$ as base cases. By making two arrays $D_1$ and $D_2$ of length $N$, we can compute these values by increasing $x$ in $O(N)$ time. EXPLANATION:Let's give some names to the different kinds of jumps.
The first thing to notice is that "quick switch" is not helpful. Let's see why this is so, by considering the various possible jumps immediately after doing a quick switch. Let's assume that Chef is at position $L_1(x)$ (the case $L_2(x)$ is essentially the same).
Thus, we have shown that forwards and slow switches are the only kinds of jumps we have to consider. A greedy approachThe remaining kinds of jumps have the property that each jump takes Chef one column to the right. In fact, we can derive a few more properties of optimal paths:
So we now have the following greedy solution to the problem:
A dynamic programming approachAnother standard way to approach the problem is to use the everpowerful dynamic programming. For some people this is simpler, because it involves less thinking about the shape of the optimal path. Let's define the distance of a block to be the minimum number of gravity switches needed to reach that block (in case the block is unreachable, we say the distance is $\infty$). Then let $D_1(x)$ and $D_2(x)$ be the distances of blocks $L_1(x)$ and $L_2(x)$, respectively. Notice that the final answer is simply $\min(D_1(N), D_2(N))$, because we want to reach either $L_1(N)$ or $L_2(N)$ as fast as possible. Now, let's focus on $D_1(x)$. If $L_1(x)$ is dirty, then of course there's no way to reach that cell (you can't even step on it!), so we immediately know that $D_1(x) = \infty$. Otherwise, the last move must have been either a "forward" or a "slow switch".
Therefore, we have the following: $$D_1(x) = \begin{cases} \infty & \text{if $L_1(x)$ is dirty} \\\ \min(D_1(x1), D_2(x1)+1) & \text{otherwise} \end{cases}$$ The case is very similar for $D_2(x)$, i.e.: $$D_2(x) = \begin{cases} \infty & \text{if $L_2(x)$ is dirty} \\\ \min(D_2(x1), D_1(x1)+1) & \text{otherwise} \end{cases}$$ These formulas enable us to compute $D_1(x)$ and $D_2(x)$ from $D_1(x1)$ and $D_2(x1)$ recursively! But what about the base cases? We can compute $D_1(1)$ and $D_2(1)$ easily by considering that Chef can start at either $L_1(1)$ or $L_2(1)$ without doing any move (as long as the block is not dirty of course!). Thus: $$D_1(1) = \begin{cases} \infty & \text{if $L_1(1)$ is dirty} \\\ 0 & \text{otherwise} \end{cases}$$ $$D_2(1) = \begin{cases} \infty & \text{if $L_2(1)$ is dirty} \\\ 0 & \text{otherwise} \end{cases}$$ But we can make the base case simpler by adding a clean block at the beginning of both lanes! This doesn't worsen the solution, because you can just start at the same lane you would have started originally, and do a "forward" move, without incurring additional gravity switches. Thus, we define two new blocks $L_1(0)$ and $L_2(0)$ as clean blocks, and define $D_1(0) = D_2(0) = 0$ as the base cases! We now have all the ingredients for our solution. First, we build two ($0$indexed) arrays, $D_1$ and $D_2$, each of length $N+1$. Then, set $D_1[0] = D_2[0] = 0$. Next, compute $D_1[x]$ and $D_2[x]$ for $1 \le x \le N$ in increasing order, based on the recurrences above. Finally, the answer is now $\min(D_1[N], D_2[N])$! (If this value is infinite, then the answer is Implementation details / optimizationsHandling $\infty$ Notice that the value $\infty$ is used in our arrays $D_1$ and $D_2$. But most builtin types (such as
I prefer the second solution. Memoryefficient DP The solution above requires us to create two arrays, $D_1$ and $D_2$. However, notice that when computing $D_1[x]$ and $D_2[x]$, we only need the values of $D_1[x1]$ and $D_2[x1]$. Therefore, we only need to store the current and previous values of $D_1$ and $D_2$, reducing the memory requirements from $O(N)$ to $O(1)$ (disregarding the memory where the input is stored)! Sample implementationsFinally, here we provide some implementations of the solution. The DP solutions use a large number for "infinity", and also use $O(1)$ additional memory. Python (Greedy approach):
C++ (Greedy approach):
Python (DP approach):
C++ (DP approach):
Time Complexity:$O(N)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 16 Aug '15, 13:05

Clearly this was an easy problem and could have been solved without dp. I recommend to add dp version as second asnwer and the simple answer as the primary answer answered 17 Aug '15, 17:54

https://www.codechef.com/viewsolution/7743518 whats wrong eith my solution !! answered 21 Aug '15, 22:31

your solution does not respond when there is not '#' in input like first test case . . second test case ... ... answered 21 Aug '15, 23:49

I made a dynamic programming solution as described in this article. I used two input methods  first cin and cout with "std::ios::sync_with_stdio(false)" and another with scanf() and printf(). The links are: https://www.codechef.com/viewsolution/7865710 https://www.codechef.com/viewsolution/7865624 I read this article and I was hoping that my first solution(cin version) will be faster than the second solution. But the opposite happened. The execution time of first submission is 0.25 seconds while for the second solution its 0.03 seconds. A similar thing happened in fifth question of August Challenge. Can someone explain this? answered 19 Aug '15, 15:48

I did the greedy one in java .Not as optimized as the above code though but logic is the same. I am getting wrong ans for last test case . Tried all possible test cases. Inputs anyone ? https://www.codechef.com/viewsolution/7739659 variable c stores the count of gravity shifts, and used exor to switch between the two lanes 0 and 1 answered 21 Aug '15, 22:00

https://www.codechef.com/viewsolution/11689125 Why is this giving wrong answer ? Tried a lot of test cases still not able to find. answered 03 Oct '16, 02:16

why is this approach wrong?? https://www.codechef.com/viewsolution/12340626 answered 25 Dec '16, 23:55
