Connection Status:
Competition Arena > LexSmallestTour

LexSmallestTour

SRM 516 · 2011-05-25 · by dolphinigle

SRM 516 · 2011-05-25 · by dolphinigle · Graph Theory
Class Name: LexSmallestTour
Return Type: int[]
Method Name: determineTour
Arg Types: (vector<string>, vector<int>)
Problem Statement

Problem Statement

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.

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.

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.

You are given a String[] roads. The j-th character of the i-th element of roads represents the road connecting city i and city j, and is either one of these :
  • '.' - no road exists.
  • 'A'-'Z', 'a'-'z' - a road exists and the type of ware that will be sold there corresponds to the letter representing it.
If there does not exist a tour for the salesman, return an empty int[]. Otherwise compute a tour that minimizes the lexicographical ordering of the cities in the order he visits them. Return a int[] containing the same number of elements as the int[] queries. The i-th element of your answer must be the number representing the (queries[i])-th city visited by the travelling salesman (0-based indexing, the 0-th city visited is the starting city, i.e., city 0).

Notes

  • 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.

Constraints

  • roads will contain between 2 and 40 elements, inclusive.
  • Each element of roads will contain N characters, where N is the number of elements in roads.
  • Each character in roads will be either '.', 'A'-'Z', or 'a'-'z'.
  • The i-th character of the i-th element of roads will be a '.'.
  • The j-th character of the i-th element of roads will be the same as the i-th character of the j-th element of roads.
  • There will be at least one road.
  • queries will contain between 1 and 50 elements, inclusive.
  • Each element of queries will be between 0 and M, inclusive, where M is the number of roads.
  • All the elements of queries will be distinct.
Examples
0)
{".A"
,"A."}
{0, 1}
Returns: { }
1)
{".AB"
,"A.C"
,"BC."}
{0, 1, 2, 3}
Returns: {0, 1, 2, 0 }

There are two possible tours: {0, 1, 2, 0} and {0, 2, 1, 0}. The first one is lexicographically earliest.

2)
{".A..C"
,"A.ABB"
,".A.C."
,".BC.."
,"CB..."}
{0, 1, 2, 3, 4, 5, 6}
Returns: {0, 1, 3, 2, 1, 4, 0 }

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.

3)
{".aa"
,"a.A"
,"aA."}
{3, 2, 1}
Returns: {0, 2, 1 }

Lowercase and uppercase letters correspond to different types of wares. The first and the last roads are not considered to be consecutive.

4)
{"..A.A"
,"...A."
,"A...A"
,".A..."
,"A.A.."}
{1, 2}
Returns: { }

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 LexSmallestTour with a public method vector<int> determineTour(vector<string> roads, vector<int> queries) · 191 test cases · 2 s / 256 MB per case

Submitting as anonymous