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

×

GRGUY - Editorial

PROBLEM LINK:

Contest
Practice

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: $$D_1(x) = \begin{cases} \infty & \text{if $L_1(x)$ is dirty} \\\ \min(D_1(x-1), D_2(x-1)+1) & \text{otherwise} \end{cases}$$ $$D_2(x) = \begin{cases} \infty & \text{if $L_2(x)$ is dirty} \\\ \min(D_2(x-1), D_1(x-1)+1) & \text{otherwise} \end{cases}$$

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: $$D_1(x) = \begin{cases} \infty & \text{if $L_1(x)$ is dirty} \\\ \min(D_1(x-1), D_2(x-1)+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(x-1), D_1(x-1)+1) & \text{otherwise} \end{cases}$$

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:

$$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 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 min function 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)$

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 16 Aug '15, 13:05

kevinsogo's gravatar image

7★kevinsogo
1.7k584142
accept rate: 11%

edited 15 Jan '16, 19:19

admin's gravatar image

0★admin ♦♦
19.6k349497539


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

link

answered 17 Aug '15, 17:54

urdarinda's gravatar image

2★urdarinda
8116
accept rate: 0%

Thanks. I added a simple solution at your recommendation :)

(17 Aug '15, 20:43) kevinsogo7★

https://www.codechef.com/viewsolution/7743518 whats wrong eith my solution !!

link

answered 21 Aug '15, 22:31

vishalrox's gravatar image

2★vishalrox
111
accept rate: 0%

@vishalrox,

your solution does not respond when there is not '#' in input like

first test case

.

.

second test case

...

...

link

answered 21 Aug '15, 23:49

admin123's gravatar image

5★admin123
1.2k12
accept rate: 28%

simple greedy works

link

answered 01 Feb, 20:57

worldunique's gravatar image

3★worldunique
1297
accept rate: 0%

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?

link

answered 19 Aug '15, 15:48

shubhambhattar's gravatar image

3★shubhambhattar
2887
accept rate: 23%

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

link

answered 21 Aug '15, 22:00

sanket407's gravatar image

4★sanket407
4849
accept rate: 10%

thanxx @admin123..!!

link

answered 22 Aug '15, 12:49

vishalrox's gravatar image

2★vishalrox
111
accept rate: 0%

https://www.codechef.com/viewsolution/11689125

Why is this giving wrong answer ? Tried a lot of test cases still not able to find.

link

answered 03 Oct '16, 02:16

vertika2011's gravatar image

2★vertika2011
1
accept rate: 0%

why is this approach wrong?? https://www.codechef.com/viewsolution/12340626

link

answered 25 Dec '16, 23:55

p_k_priyanka's gravatar image

2★p_k_priyanka
1
accept rate: 0%

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,182
×2,022
×1,132
×970
×186

question asked: 16 Aug '15, 13:05

question was seen: 5,918 times

last updated: 01 Feb, 20:57