UnreliableRover
TCO19 SRM 748 · 2019-01-09 · by misof
Problem Statement
We have secretly deployed our autonomous own Mars rover. It landed in the middle of a large flat area. From the point of view of the rover, the surface of Mars is an infinite plane divided into squares with side length 1 meter. The sides of the grid are aligned with the cardinal direction (North-South and East-West).
The rover moves in steps. In each step it moves into the next square in one of the four directions. The rover decides how to move based on some complex measurements and calculations it makes, so it's movement is completely unpredictable for us on Earth.
The rover reports its movements back to our homebase. The reports are sent in compressed form: first a direction it chose, then the number of steps it took in that direction. However, the error-correcting codes we built into the rover turned out to be insufficient, so sometimes we get garbage and a part of the information transmitted by the rover gets lost.
We know the exact starting coordinates of the rover. From that point, the rover has made a sequence of movements and it reported them in the above form, in chronological order. You are given the information we could reconstruct from what we received. Namely:
- The
String direction. For each i, direction[i] is either one of "NEWS" if we know the rover's direction of movement for its report number i, or '?' if we don't know it. - The
int[] s minSteps and maxSteps. These are giving you the information that the number of steps in report number i could have been any integer between minSteps[i] and maxSteps[i], inclusive. Additionally, whenever direction[i] is '?', minSteps[i] is 0. (In that case, the number of steps could be arbitrarily small, and it is even possible that there was no movement at all.)
Compute and return the area (in square meters) of the region where our rover can currently be located.
Constraints
- direction will contain between 1 and 50 characters, inclusive.
- Each character in direction will be one of "NEWS?".
- direction will contain at most 20 copies of the '?' character.
- minSteps and maxSteps will each have the same number of elements as the number of characters in direction.
- For each valid i, 0 <= minSteps[i] <= maxSteps[i] <= 10^7.
- For each valid i, if direction[i] = '?' then minSteps[i] will be 0.
"N"
{3}
{5}
Returns: 3
The rover started at (0,0) and after 3-5 steps northwards it ended at (0,3), (0,4), or (0,5).
"NE"
{3,3}
{5,5}
Returns: 9
The rover ended at one of the cells (x,y) witn 3 <= x,y <= 5.
"?"
{0}
{2}
Returns: 9
The rover can end at any of the squares (-2,0), (-1,0), (0,-2), (0,-1), (0,0), (0,1), (0,2), (1,0), or (2,0).
"??N?"
{0, 0, 0, 0}
{0, 0, 0, 0}
Returns: 1
The rover is still where it started.
"??E?"
{0, 0, 3, 0}
{2, 3, 4, 2}
Returns: 120
Submissions are judged against all 80 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class UnreliableRover with a public method long long getArea(string direction, vector<int> minSteps, vector<int> maxSteps) · 80 test cases · 2 s / 256 MB per case