FIGBOT - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: nskybytskyi
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given a string S containing the characters \texttt{U,D,L,R}, representing the movement of Alice’s robot on the 2-D plane. It starts at (0, 0).
If Bob’s robot starts at (X, Y), does there exist a sequence of moves that will allow him to occupy the same position as Alice’s robot at some instant of time?

EXPLANATION:

Let’s try to solve a single instance of the problem: can Bob occupy the same position as Alice after exactly i moves have been made?

To answer that, first let’s compute where Alice’s robot will be: say (x_i, y_i).
This can be found by just directly simulating movements.

Now, if Bob is to reach exactly this position, note that he must make |x_i - X| horizontal moves and |y_i - Y| vertical moves.
So, if |x_i - X| + |y_i - Y| \gt i, Bob definitely cannot reach this position, no matter what - he simply doesn’t have enough movement to do so.

On the other hand, if |x_i - X| + |y_i - Y| \lt i, Bob has some ‘extra’ moves left with him that need to be exhausted.
If these extra moves are even in number, Bob can easily use them all up (for example, alternate moving up and down), and still be at (x_i, y_i) after i seconds have passed.
If the number of extra moves is odd, there is no way for Bob to ever remain at (x_i, y_i) after using them all up.

Why?

A helpful observation here is to look at parity - that is, whether numbers are odd or even.
Notice that each move Bob makes changes the parity of either his x-coordinate, or his y-coordinate (but not both).

If Bob makes an odd number of moves, either his x-coordinate or his y-coordinate will change an odd number of times - and hence will have different parity from what it started with.
If two numbers have different parity, they definitely cannot be equal; so since Bob has some coordinate with a different parity, he cannot be at the position he started at.

So, once x_i and y_i are known, we can figure out whether Bob can reach (x_i, y_i) in exactly i moves with a couple of simple checks.
Try this for every i from 1 to N, to see if Bob can reach Alice at any point along her path - the answer is Yes if at least one check passes, and No if they all fail.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, x, y = map(int, input().split())
    s = input()
    ax, ay = 0, 0
    ans = 'No'
    for i in range(n):
        if s[i] == 'R': ax += 1
        if s[i] == 'L': ax -= 1
        if s[i] == 'U': ay += 1
        if s[i] == 'D': ay -= 1

        dx, dy = abs(x-ax), abs(y-ay)
        if dx+dy <= i+1 and (dx+dy)%2 == (i+1)%2: ans = 'Yes'
    print(ans)
1 Like
2

Hi, my solution passes all tests, however it does not check if the number of remaining moves is even. Is there something that I am missing here or maybe there is something wrong with the tests used to assess that problem?

Here is the code:

#include <bits/stdc++.h>
using namespace std;

int dist(int x, int y, int a, int b) {
    return abs(x - a) + abs(y - b);
}

void solve() {
    int n, x, y;
    string S;
    cin >> n >> x >> y >> S;
    int a = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (S[i] == 'U') b++;
        if (S[i] == 'D') b--;
        if (S[i] == 'L') a--;
        if (S[i] == 'R') a++;
        if (dist(x, y, a, b) == i + 1) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

int main() {
	// your code goes here
    int t;
    cin >> t;
    while (t--) solve();
}
3

You are checking for equality instead of inequality, and equality cannot happen with wrong parity.

1 Like
4

can you explain what you have said parity ?

5

In the code above, the parity of dist(x, y, a, b), which is |x - a| + |y - b| changes with every operation. If it was odd before the operations then after apply s[i] with i = 0 it will be even, and an even number cannot be equal to i + 1 = 1 which is an odd number. After applying s[i] with i = 1 the parity of dist(x, y, a, b) will change to odd, and an odd number cannot be equal to i + 1 = 2 which is an even number, etc.

6

I can’t understand. Please explain me

7

Is there exist any test case where distance will be less than i+1 and parity are same. But for this case there does not exists distance == i+1

8

Ok, I think I got, let me explain it in my own words.

Let’s denote R_i as range of Bob’s robot, i.e how much distance can he travel from his position (X,Y) at moment i. Obviously R_i = i (for convenience i = 1 is the first move). Now, let’s denote D_i as distance of Alice’s robot from (X,Y) at time i. This variable depends on string S. We can see that with our definition of distance (|x_i - X| + |y_i - Y|) we can only have D_{i + 1} = D_i + 1 or D_{i +1} = D_i - 1 (the move of robot changes only one coordinate and quick examination shows that those are only possible situations).

Now let’s consider the difference D_i - R_i. From our observation and definition of R_i we can see that either D_{i + 1} - R_{i + 1} = D_i - R_i or D_{i + 1} - R_{i + 1} = D_i - R_i - 2. From constraints of our problem we have (X,Y) \neq (0, 0), thus D_0 > 0 and R_0 = 0, hence D_0 - R_0 > 0. If for any i we have the following satisfied:

if dx+dy <= i+1 and (dx+dy)%2 == (i+1)%2: ans = 'Yes'

then it means that now D_i - R_i < 0 and D_i - R_i is divisible by 2. But since this expression with every iteration either remains constant or decreases by 2 it must have achieved 0 at some point, since it was positive at the beginning.

1 Like
9

I tried your solution, and it passes. Something must be wrong with the the tests.