-
Notifications
You must be signed in to change notification settings - Fork 24
/
Copy pathLexSmallestTour.html
27 lines (27 loc) · 6.46 KB
/
LexSmallestTour.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>A travelling salesman is going to sell his wares in Graph Country. There are N cities in the country numbered 0 through N-1 and several bidirectional roads connecting pairs of cities.
<br></br>
<br></br>
As his name suggests, the travelling salesman sells his wares while travelling. He will start in city 0, traverse each of the roads in the country exactly once, and end up back in city 0. Furthermore, he has done a survey and has decided which ware to sell on each road. The types of the wares are represented by letters 'A'-'Z' and 'a'-'z' (uppercase and lowercase letters are considered distinct) and he's going to sell exactly one type of ware on each road.
<br></br>
<br></br>
To avoid getting bored, he doesn't want to sell the same type of ware on two consecutive roads that he traverses. Two roads are consecutive if he traverses one of the roads directly after traversing the other road. Note that the final road he traverses is not considered to be consecutive to the first road he traverses.
<br></br>
<br></br>
You are given a vector <string> <b>roads</b>. The j-th character of the i-th element of <b>roads</b> represents the road connecting city i and city j, and is either one of these :
<ul>
<li>'.' - no road exists.</li>
<li>'A'-'Z', 'a'-'z' - a road exists and the type of ware that will be sold there corresponds to the letter representing it.</li>
</ul>
If there does not exist a tour for the salesman, return an empty vector <int>. Otherwise compute a tour that minimizes the lexicographical ordering of the cities in the order he visits them. Return a vector <int> containing the same number of elements as the vector <int> <b>queries</b>. The i-th element of your answer must be the number representing the (<b>queries[i]</b>)-th city visited by the travelling salesman (0-based indexing, the 0-th city visited is the starting city, i.e., city 0).</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>LexSmallestTour</td></tr><tr><td>Method:</td><td>determineTour</td></tr><tr><td>Parameters:</td><td>vector <string>, vector <int></td></tr><tr><td>Returns:</td><td>vector <int></td></tr><tr><td>Method signature:</td><td>vector <int> determineTour(vector <string> roads, vector <int> queries)</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>Notes</h3></td></tr><tr><td align="center" valign="top">-</td><td>The lexicographical ordering of the cities in a tour is less than in another tour of the same length if, at the first city in which the two tours differs, the number of the city for the first tour is less than the number of the city for the second tour.</td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>roads</b> will contain between 2 and 40 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>roads</b> will contain N characters, where N is the number of elements in <b>roads</b>.</td></tr><tr><td align="center" valign="top">-</td><td>Each character in <b>roads</b> will be either '.', 'A'-'Z', or 'a'-'z'.</td></tr><tr><td align="center" valign="top">-</td><td>The i-th character of the i-th element of <b>roads</b> will be a '.'.</td></tr><tr><td align="center" valign="top">-</td><td>The j-th character of the i-th element of <b>roads</b> will be the same as the i-th character of the j-th element of <b>roads</b>.</td></tr><tr><td align="center" valign="top">-</td><td>There will be at least one road.</td></tr><tr><td align="center" valign="top">-</td><td><b>queries</b> will contain between 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>queries</b> will be between 0 and M, inclusive, where M is the number of roads.</td></tr><tr><td align="center" valign="top">-</td><td>All the elements of <b>queries</b> will be distinct.</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>{".AB"
,"A.C"
,"BC."}</pre></td></tr><tr><td><pre>{0, 1, 2, 3}</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0, 1, 2, 0 }</pre></td></tr><tr><td><table><tr><td colspan="2">There are two possible tours: {0, 1, 2, 0} and {0, 2, 1, 0}. The first one is lexicographically earliest.</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>{".A..C"
,"A.ABB"
,".A.C."
,".BC.."
,"CB..."}</pre></td></tr><tr><td><pre>{0, 1, 2, 3, 4, 5, 6}</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0, 1, 3, 2, 1, 4, 0 }</pre></td></tr><tr><td><table><tr><td colspan="2">It's impossible to sell the same type of wares on two consecutive roads, so, for example, {0, 1, 2, 3, 1, 4, 0} is not a valid tour.</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>{".aa"
,"a.A"
,"aA."}</pre></td></tr><tr><td><pre>{3, 2, 1}</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0, 2, 1 }</pre></td></tr><tr><td><table><tr><td colspan="2">Lowercase and uppercase letters correspond to different types of wares. The first and the last roads are not considered to be consecutive.</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>{"..A.A"
,"...A."
,"A...A"
,".A..."
,"A.A.."}</pre></td></tr><tr><td><pre>{1, 2}</pre></td></tr></table></td></tr><tr><td><pre>Returns: { }</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>