LongSimplePath
SRM 849 · 2023-09-27 · by misof
Problem Statement
A robot is placed on an infinite plane that is divided into a grid of unit squares. The robot's starting square has coordinates (0, 0). Your goal is to move the robot to the square with coordinates (R, C).
The robot understands only two types of commands:
- The commands labeled using lowercase English letters (a, b, c, ...) instruct the robot to walk into higher-numbered rows.
- The commands labeled using uppercase English letters (A, B, C, ...) instruct the robot to walk into higher-numbered columns.
More precisely:
- For i=0 to 25, the command 'a'+i instructs the robot to walk from its current square (r,c) to the square (r+2^i,c).
- For i=0 to 25, the command 'A'+i instructs the robot to walk from its current square (r,c) to the square (r,c+2^i).
For example, the program "bDa" will cause the robot to do the following:
- 'b': Walk from (0,0) via (1,0) to (2,0).
- 'D': Walk from (2,0) via (2,1), ..., (2,7) to (2,8).
- 'a': Walk from (2,8) to (3,8).
Some squares in the robot's plane may be blocked. You are given the coordinates of all these obstacles: for each valid i, the square (obsR[i], obsC[i]) is blocked. The robot may not enter these squares. This includes entering them during the execution of a command. E.g., in the above example, if there were an obstacle at (2,5), the instruction 'D' would cause the robot to collide with the obstacle.
If the target square cannot be reached, return an empty string.
It can be shown that whenever the target square can be reached, there is always a program of 3,000 or fewer instructions that gets the robot exactly to the target square. Find and return any one such program.
Notes
- Any valid solution will be accepted. In particular, you are not required to minimize the number of instructions in your program.
Constraints
- R will be between 0 and 10^9, inclusive.
- C will be between 0 and 10^9, inclusive.
- R+C will be positive.
- obsR will contain between 0 and 50 elements, inclusive.
- obsC will contain the same number of elements as obsR.
- Each element of obsR will be between 0 and R, inclusive.
- Each element of obsC will be between 0 and C, inclusive.
- All obstacles described by obsR and obsC will be in mutually distinct squares.
- The cells (0, 0) and (R, C) will not contain an obstacle.
0
6
{}
{}
Returns: "CB"
We just need to tell the robot to take six steps "to the right" (from column 0 to column 6).
0
6
{0}
{4}
Returns: ""
Same as the previous example, but now the obstacle is preventing us from reaching the goal.
2
2
{0, 2}
{2, 0}
Returns: "AaAa"
The board looks as follows (with 'R' being the robot, '.' being empty squares, 'X' being obstacles, and '*' being the target square): X.* ... R.X The correct solutions for this test case are precisely the following strings: "aBa", "aAAa", "aAaA", "AbA", "AaaA", and "AaAa". You may return any of these six strings.
123
456
{0, 122}
{1, 456}
Returns: "gfedaIHGCBAbA"
Here the two obstacles limit the directions in which we can leave the start and reach the goal.
123456789
2
{12345678, 23456789, 34567890}
{0, 1, 2}
Returns: ""
3
1234
{0, 1, 2, 3}
{7, 7, 111, 111}
Returns: ""
Remember that our robot can only go "up" and "right". These four obstacles are enough to prevent it from being able to reach the goal.
Submissions are judged against all 170 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LongSimplePath with a public method string traverse(int R, int C, vector<int> obsR, vector<int> obsC) · 170 test cases · 2 s / 256 MB per case