UKROBOT - Editorial

PROBLEM LINK:

Division 1
Division 2
Practice

Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen

(My) video
Official video

DIFFICULTY:

Easy

PREREQUISITES:

Simple Math, Observations

PROBLEM:

NOTE: For some reason unbeknownst to me (and the setter, apparently), R and C were switched mid-contest. So you may have to swap R and C for everything in this editorial too. I’m not really sure; my/our solutions still seem to pass.

There’s a robot in an infinite grid which starts at (0, 0), and a single obstacle positioned at (x, y), where 1 \leq x \leq c and 1 \leq y \leq r. You want to give the robot some sequence of movement instructions (up, down, left, or right). If a robot has an instruction that will move it into the obstacle, it will skip that instruction. After all the instructions have been performed, for all possible locations for the obstacle, given only the final position of the robot, you should be able to deduce where the obstacle is. Find any possible sequence of instructions.

QUICK EXPLANATION:

Subtask 1

The following sequence works: U + 20*R

Main solution

The following sequence works: U + 20*R + 20*L + U + 40*R + 40*L + U + ... + U + 400*R + 400*L

EXPLANATION:

Subtask 1

Consider having moved up to the row where the obstacle is. Then, if we move infinitely to the right, we’ll eventually hit the obstacle and stop right before it, therefore being able to deduce its location from where we stopped. We don’t have infinite operations, but we can simulate infinity by moving right 20 times, which is enough to hit the obstacle no matter where it is.

You can also do it with 19 moves to the right. It doesn’t really matter, we’re not trying to minimize the number of instructions.

Main solution

Unlike in subtask 1, we can have more than 1 row this time, meaning the obstacle won’t necessarily stop us completely. However, we don’t need the obstacle to stop us, we only need the information about which instructions the obstacle blocks.

Each position of the obstacle will block some (potentially empty) subset of our instructions and displace us (from our ending point without an obstacle) by some amount (\Delta x, \Delta y). We want to make all of these displacements different, as otherwise, we would have no way of telling the difference between multiple obstacle locations mapping to a single displacement.

This problem is completely constructive, so we can try various options to simplify our construction. For example, we can try fixing \Delta y = 0, and every obstacle location would have to map to a specific \Delta x. It turns out this path works out, although there may be others that also lead to a possible solution.

At first glance, it seems like there are too many \Delta x values to represent, and we’ll go over our bound of 10^4 operations. But we can once again simplify by going through entire rows at once. That is, let’s go through the bottommost (y = 1) row first and all at once, then the next higher one (y = 2), etc.

Say we make k moves to the right, starting at x = 0. Then, if the obstacle is in that row and at column i, k - i + 1 of those moves will be blocked - that is, \Delta x = k - i + 1 (maybe negative, doesn’t matter). We can then return to x = 0 by making k moves to the left afterwards (if we hit the obstacle and thus don’t return to x = 0, it’s fine, because we won’t ever hit another obstacle). If we use a different k for each row, we can cover many possible values of \Delta x. A value of k will cover \Delta x in the range [k - m + 1, k], so if we start k at m and increase it by m each row, no values of \Delta x will intersect and we’ll have a solution.

The total moves we use is n + \sum{2k}, which is on the order of 8420, so we fit within the length bound comfortably. Of course, there are many ways to reduce it further.

Note that this solution is inconsistent with my own quick explanation. We can increase k by an arbitrary amount \geq m each time, and even visit extra rows if we want; it’ll still work. That’s the magic of constructive problems - there are so many different solutions of varying levels of convenience.

TIME COMPLEXITY:

Subtask 1

O(1), but technically O(c).

Main solution

O(r^2c) or O(c^2r) or a large constant O(1), depending on how you implement.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
 
    int R, C;
    cin>>R>>C;
    for (int i = 0; i<20; i++)
    {
        cout<<"U";
        for (int j = 0; j<20*(i+1); j++) cout<<"R";
        for (int j = 0; j<20*(i+1); j++) cout<<"L";
    }
}
Tester's Solution
#include <bits/stdc++.h>
 
using namespace std;
using nagai = long long;
 
int main() {
	 cin.tie(0);
	 ios::sync_with_stdio(false);
	 for(int i=1;i<=21;++i) {
		 for(int j=0;j < 21 * i; ++j)
			 cout << 'U';
		 for(int j=0;j < 21 * i; ++j)
			 cout << 'D';
		 cout << 'R';
	 }
	 cout << '\n';
	 return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL); cout.tie(NULL);}
typedef long long ll;
 
void solve(int tc = 0) {
	ll n, m;
	cin >> n >> m;
	
	cout << "U";
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < m * (i + 1); j++) {
			cout << "R";
		}
		for (ll j = 0; j < m * (i + 1); j++) {
			cout << "L";
		}
		cout << "U";
	}
}
 
int main() {
	send help
	
	int tc = 1;
	// cin >> tc;
	for (int t = 0; t < tc; t++) solve(t);
}  

Video Editorial(s)

My video: CodeChef September Lunchtime 2020 - All Solutions (Div. 1 + Div. 2) - YouTube
Official video: - YouTube

13 Likes

Is it a bad idea to circularly traverse the r*c grid? I employed this approach but got WA.
Solution link: CodeChef: Practical coding for everyone

Visual representation of my logic:

Start at (0,0), and follow the red lines. Example case r=4,c=4.

4 Likes

That lets you visit all the squares, but how can you uniquely determine the position of the obstacle? Remember, you’re only given the robot’s final position (and all of them ultimately have to be unique).

4 Likes

Ah yes, that makes sense. I underthought it lol

My bad! :sweat_smile:

What will happen if the bot finds an obstacle, whether it will stop there forever or move again if it finds some instructions which satisfy it’s moving rule?

If it has an instruction which will move it into the obstacle, it ignores it, meaning it may do other instructions that don’t force it into the obstacle.

1 Like

I don’t get this part …

In the problem statement, it’s stated that :

When performing an instruction, if the cell it needs to move to is free, then it moves to that cell; otherwise, it stays in its current cell.

So, if the robot is sent to the square with the obstacle, it should stop, right ?
So, why visiting all the possible cells minus 1 is not enough to know the obstacle position ?

3 Likes

nevermind … I see the issue now …

1 Like

I have a little confusion about dircetions.

for subtask 1.

L: move one cell to the left, i.e. from a cell (x,y) to (x−1,y)
R: move one cell to the right, i.e. from a cell (x,y) to (x+1,y)
D: move one cell down, i.e. from a cell (x,y) to (x,y−1)
U: move one cell up, i.e. from a cell (x,y) to (x,y+1)

then U + 20*R will generate sequence like this (00 01 11 21 31 41 51) then how can x be
1<=X<=R (row) ?

1 Like

According to given problem statement, 1<=x<=r && 1<=y<=c ;
According to editorial, 1<=x<=c && 1<=y<=r ;
I think they are different.

1 Like

I am having a feeling that either the question was not well written , or my English is bad as even after 2-3 readings I was unable to understand the problem…

17 Likes

The question says X<=R and Y<=C. You have taken the reverse here. Am i missing anything or is there a misprint in the question?

1 Like

Yeah. Terminology was a bit confusing. R is the number of “rows” - y-positions, and C is the number of “columns” - x-positions.

edit: I think this is wrong

1 Like

Yes,It is wrong not only in editorial but testing too.
when I reversed the r and c in my solution my solution got AC.

1 Like

This line should have been added in the question. Most people interpreted that the robot would just stay immobile after encountering an obstacle. Anyways good problem.

1 Like

There was an announcement regarding the same in the middle of the contest.
I missed the change too :confused:

Statement of UKROBOT had 1 <= X <= C, 1 <= Y <= R, instead of 1 <= X <= R, 1 <= Y <= C, it is fixed now.

this is from announcements.

So I think question was correct but after announcement it got wrong.

1 Like

Yeah… I have considered it will be immobile after it find an obstacle, That’s why I was not able to figure out why I am getting WA

Shit! I misunderstood this problem

1 Like

Exactly!