RouteIntersection
Member Single Round Match 474 · 2009-12-03 · by maksay
Member Single Round Match 474 · 2009-12-03 · by maksay · Dynamic Programming, Encryption/Compression
Problem Statement
Problem Statement
Little Dazdraperma likes to travel a lot. One day she made a route in an N-dimensional space. In this space each point is represented by N coordinates. The coordinates are indexed from 1 to N, inclusive. She started from the origin, i.e., a point where each coordinate is 0. Then she did several moves of the following type:
int[] coords and a String moves representing her route. The i-th element of coords is the coordinate index she has chosen during her i-th move. If the coordinate with this index was increased during the i-th move, the i-th character of moves will be '+', and it will be '-' if this coordinate was decreased.
Return "VALID" if all points of her route were unique, including the first and the last points, and return "NOT VALID" otherwise. Two points A and B in N-dimensional space are different if there's an index i such that A's coordinate with index i and B's coordinate with index i are different.
- First she chose a coordinate index, i.e., a number between 1 and N, inclusive.
- Then she jumped to a point where the coordinate with the chosen index is either increased or decreased by 1 and all other coordinates remain the same.
Return "VALID" if all points of her route were unique, including the first and the last points, and return "NOT VALID" otherwise. Two points A and B in N-dimensional space are different if there's an index i such that A's coordinate with index i and B's coordinate with index i are different.
Constraints
- N will be between 1 and 1000000000 (109), inclusive.
- coords will contain between 1 and 50 elements, inclusive.
- Each element of coords will be between 1 and N, inclusive.
- moves will contain the same number of characters as the number of elements in coords.
- Each character in moves will be either '+' or '-'.
Examples
0)
1
{1}
"+"
Returns: "VALID"
Dazdraperma starts at (0) and then jumps to (1). The answer is "VALID".
1)
2
{1,2,1,2}
"++--"
Returns: "NOT VALID"
The route goes through 5 points: (0,0) -> (1,0) -> (1,1) -> (0,1) -> (0,0). The point (0,0) was visited twice.
2)
3
{1,2,3,1,2}
"+++--"
Returns: "VALID"
(0,0,0) -> (1,0,0) -> (1,1,0) -> (1,1,1) -> (0,1,1) -> (0,0,1).
3)
344447
{132,51717,628,344447,628,51717,344447,2}
"+-++-+--"
Returns: "NOT VALID"
The repeated point doesn't have to be the first or the last point in the route.
4)
1
{1,1}
"+-"
Returns: "NOT VALID"
Submissions are judged against all 191 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RouteIntersection with a public method string isValid(int N, vector<int> coords, string moves) · 191 test cases · 2 s / 256 MB per case