TopCoder problem "RouteIntersection" used in Member Single Round Match 474 (Division I Level One , Division II Level Two)



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:
  • 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.
Now Dazdraperma wonders whether she has ever visited the same point twice. You will be given a 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.
 

Definition

    
Class:RouteIntersection
Method:isValid
Parameters:int, int[], String
Returns:String
Method signature:String isValid(int N, int[] coords, String moves)
(be sure your method is public)
    
 

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"
5)
    
990630
{833196,524568,361663,108056,28026,824639,269315,440977,440977,765458,
988451,242440,948414,130873,773990,765458,130873,28026,853121,553636,
581069,82254,735536,833196,898562,898562,940783,988451,540613,317306,
623194,940783,571384,988451,108056,514374,97664}
"--+---+-+++-+-+---++-++-+---+-+--+-++"
Returns: "NOT VALID"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10804

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14185&pm=10804

Writer:

maksay

Testers:

Rustyoldman , ivan_metelsky , mohamedafattah , it4.kp , K.A.D.R

Problem categories:

Dynamic Programming, Encryption/Compression