PROBLEM LINK:
Division 1
Division 2
Practice
Author: Anton Trygub
Tester: Alexander Morozov
Editorialist: Colin Galen
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