forked from daiwb/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRouteIntersection.html
More file actions
14 lines (14 loc) · 5.96 KB
/
RouteIntersection.html
File metadata and controls
14 lines (14 loc) · 5.96 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
<html><body bgcolor="#cccccc" text="#000000"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>
Little Dazdraperma likes to travel a lot. One day she made a route in an <b>N</b>-dimensional space. In this space each point is represented by <b>N</b> coordinates. The coordinates are indexed from 1 to <b>N</b>, inclusive. She started from the origin, i.e., a point where each coordinate is 0. Then she did several moves of the following type:
<ul>
<li> First she chose a coordinate index, i.e., a number between 1 and <b>N</b>, inclusive.</li>
<li> 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.</li>
</ul>
Now Dazdraperma wonders whether she has ever visited the same point twice. You will be given a vector <int> <b>coords</b> and a string <b>moves</b> representing her route. The i-th element of <b>coords</b> 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 <b>moves</b> will be '+', and it will be '-' if this coordinate was decreased.
<br></br>
<br></br>
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 <b>N</b>-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.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>RouteIntersection</td></tr><tr><td>Method:</td><td>isValid</td></tr><tr><td>Parameters:</td><td>int, vector <int>, string</td></tr><tr><td>Returns:</td><td>string</td></tr><tr><td>Method signature:</td><td>string isValid(int N, vector <int> coords, string moves)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td>    </td></tr><tr><td></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>N</b> will be between 1 and 1000000000 (10<sup>9</sup>), inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>coords</b> will contain between 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>coords</b> will be between 1 and <b>N</b>, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>moves</b> will contain the same number of characters as the number of elements in <b>coords</b>.</td></tr><tr><td align="center" valign="top">-</td><td>Each character in <b>moves</b> will be either '+' or '-'.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>1</pre></td></tr><tr><td><pre>{1}</pre></td></tr><tr><td><pre>"+"</pre></td></tr></table></td></tr><tr><td><pre>Returns: "VALID"</pre></td></tr><tr><td><table><tr><td colspan="2">Dazdraperma starts at (0) and then jumps to (1). The answer is "VALID".</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>2</pre></td></tr><tr><td><pre>{1,2,1,2}</pre></td></tr><tr><td><pre>"++--"</pre></td></tr></table></td></tr><tr><td><pre>Returns: "NOT VALID"</pre></td></tr><tr><td><table><tr><td colspan="2">The route goes through 5 points:
(0,0) -> (1,0) -> (1,1) -> (0,1) -> (0,0). The point (0,0) was visited twice.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>3</pre></td></tr><tr><td><pre>{1,2,3,1,2}</pre></td></tr><tr><td><pre>"+++--"</pre></td></tr></table></td></tr><tr><td><pre>Returns: "VALID"</pre></td></tr><tr><td><table><tr><td colspan="2">(0,0,0) -> (1,0,0) -> (1,1,0) -> (1,1,1) -> (0,1,1) -> (0,0,1).</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>344447</pre></td></tr><tr><td><pre>{132,51717,628,344447,628,51717,344447,2}</pre></td></tr><tr><td><pre>"+-++-+--"</pre></td></tr></table></td></tr><tr><td><pre>Returns: "NOT VALID"</pre></td></tr><tr><td><table><tr><td colspan="2">The repeated point doesn't have to be the first or the last point in the route.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>1</pre></td></tr><tr><td><pre>{1,1}</pre></td></tr><tr><td><pre>"+-"</pre></td></tr></table></td></tr><tr><td><pre>Returns: "NOT VALID"</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">5)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>990630</pre></td></tr><tr><td><pre>{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}</pre></td></tr><tr><td><pre>"--+---+-+++-+-+---++-++-+---+-+--+-++"</pre></td></tr></table></td></tr><tr><td><pre>Returns: "NOT VALID"</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>