PROBLEM LINK:
Author: Sunny Agarwal
Tester: Hiroto Sekido
Editorialist: Kevin Atienza
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):
- Go to the $(x+1)$th block of the same lane.
- Switch gravity and go to the x th block of the other lane.
- Switch gravity and go to the $(x+1)$th block of the other 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 is no path to the end path if and only if there is a column where both lanes contain dirty blocks.
- If there is a lane containing no dirty blocks, then the minimum number of gravity switches is 0.
- Otherwise, start at the lane whose first dirty block appears later. Only switch lanes if the next block in the current lane is dirty. The number of steps taken is the answer.
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:
- The answer is \min(D_1(N), D_2(N))
- We have the recurrences:
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.
- Forward: Go to the $(x+1)$th block of the same lane.
- Quick switch: Switch gravity and go to the x th block of the other lane.
- Slow switch: Switch gravity and go to the $(x+1)$th block of the other lane.
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).
- If the next jump is a “forward”, then you went from L_1(x) to L_2(x+1) with one gravity switch. But this is just like doing a “slow switch”! If we do a single “slow switch” instead, the number of gravity switches stays the same, and we skipped passing through the block L_2(x) (which is actually better in case L_2(x) is dirty).
- If the next jump is a “slow switch”, then you went from L_1(x) to L_1(x+1) with two gravity switches. But we can instead do a single “forward” move without doing any gravity switches! (and we skipped passing through the block L_2(x) which is helpful as explained in the previous bullet)
- If the next jump is another “quick switch”, then you just went back to your original position while incurring two gravity switches. Clearly, doing two quick switches in a row is just a waste of effort.
Thus, we have shown that forwards and slow switches are the only kinds of jumps we have to consider.
A greedy approach
The 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:
- It’s not optimal to slow switch if there is no obstacle to avoid. More specifically, if you did a slow switch, then a sequence of k forwards, and another slow switch, but there weren’t any dirty blocks that were avoided in the process, then you can just replace that sequence with a sequence of k+2 forward switches. This saves you two gravity switches
- It’s always better to start at the lane whose first dirty block appears later, or doesn’t appear at all. This is because if you start at the other lane, you are forced to do a slow switch which you could have avoided by simply starting at the other lane.
So we now have the following greedy solution to the problem:
- There is no path to the end path if and only if there is a column where both lanes contain dirty blocks.
- If there is a lane containing no dirty blocks, then the minimum number of gravity switches is 0.
- Otherwise, start at the lane whose first dirty block appears later, and simulate the path by trying to do only “forward” steps. Only use “slow switch” if the next block is dirty. The number of steps taken is the answer.
A dynamic programming approach
Another standard way to approach the problem is to use the ever-powerful 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”.
- If it was a forward, then you arrived at L_1(x-1) to get to L_1(x). The minimum number of gravity switches required for this is D_1(x-1).
- If it was a slow switch, then you arrived at L_2(x-1) to get to L_1(x). The minimum number of gravity switches required for this is D_2(x-1) + 1 (the +1 is due to the last move which uses one gravity switch).
Therefore, we have the following:
The case is very similar for D_2(x), i.e.:
These formulas enable us to compute D_1(x) and D_2(x) from D_1(x-1) and D_2(x-1) 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:
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 No)
Implementation details / optimizations
Handling \infty
Notice that the value \infty is used in our arrays D_1 and D_2. But most builtin types (such as int or long) do not have infinite values. Here are possible ways to handle that:
- Use a dummy value such as “-1” in place of infinity. I don’t recommend this though, because you’ll have to check for the value “-1” all the time (for example, you need to modify the
minfunction because infinity should be larger than all other elements). - Define “infinity” to be some large value. Some possibilities are 10^9, 2^{30}, 2^{60} or the data type’s upper limit. This has the advantage that comparisons of infinity against normal values are correct. However, one should be careful in comparing “infinite” values against each other. Also, be careful in doing arithmetic with this “infinity”, because you might incur overflow!
- Use the “float” or “double” data type which have infinite values.
I prefer the second solution.
Memory-efficient 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[x-1] and D_2[x-1]. 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 implementations
Finally, 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):
INF = 1<<30 # some really large number
for cas in xrange(input()):
L1 = raw_input()
L2 = raw_input()
ans = 0
curr = 0
for L1x, L2x in zip(L1, L2):
if L1x == L2x == '#':
ans = INF
break
if L1x == '#':
if curr == 1:
ans += 1
curr = 2
if L2x == '#':
if curr == 2:
ans += 1
curr = 1
if ans >= INF:
print "No"
else:
print "Yes"
print ans
C++ (Greedy approach):
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LIM 200011
#define INF LIM<<3
char words[2][LIM];
int main() {
int z;
scanf("%d", &z);
while (z--) {
scanf("%s%s", words[0], words[1]);
int n = strlen(words[0]);
int curr = -1, ans = 0;
for (int i = 0; i < n; i++) {
bool dirty0 = words[0][i] == '#';
bool dirty1 = words[1][i] == '#';
if (dirty0 && dirty1) {
ans = INF;
break;
}
if (dirty0) {
if (curr == 0) ans++;
curr = 1;
}
if (dirty1) {
if (curr == 1) ans++;
curr = 0;
}
}
if (ans >= INF) {
printf("No\n");
} else {
printf("Yes\n%d\n", ans);
}
}
}
Python (DP approach):
INF = 1<<30 # some really large number
for cas in xrange(input()):
L1 = raw_input()
L2 = raw_input()
D1 = D2 = 0
for L1x, L2x in zip(L1, L2):
D1, D2 = (
INF if L1x == '#' else min(D1, D2 + 1),
INF if L2x == '#' else min(D2, D1 + 1),
)
ans = min(D1, D2)
if ans >= INF:
print "No"
else:
print "Yes"
print ans
C++ (DP approach):
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LIM 200011
#define INF (LIM<<3)
char L[2][LIM];
int D[2];
int nD[2];
int main() {
int z;
scanf("%d", &z);
while (z--) {
scanf("%s%s", L[0], L[1]);
int n = strlen(L[0]);
D[0] = D[1] = 0;
for (int i = 0; i < n; i++) {
nD[0] = L[0][i] == '#' ? INF : min(D[0], D[1] + 1);
nD[1] = L[1][i] == '#' ? INF : min(D[1], D[0] + 1);
D[0] = nD[0];
D[1] = nD[1];
}
int ans = min(D[0], D[1]);
if (ans >= INF) {
printf("No\n");
} else {
printf("Yes\n%d\n", ans);
}
}
}
Time Complexity:
O(N)
