Connection Status:
Competition Arena > GreedyTravelingSalesman

GreedyTravelingSalesman

TCO12 Parallel Round 2C · 2012-03-27 · by ir5

TCO12 Parallel Round 2C · 2012-03-27 · by ir5 · Brute Force, Graph Theory
Class Name: GreedyTravelingSalesman
Return Type: int
Method Name: worstDistance
Arg Types: (vector<string>, vector<string>, vector<string>, vector<string>)
Problem Statement

Problem Statement

In Digraph Country, there are N cities indexed 0 through N-1. Each pair of different cities is connected by two one-way roads, one in each direction. The lengths of roads may be asynmetric. I.e., it is possible that the road from i to j and the road from j to i have different lengths.

A travelling salesman wants to visit each city of the country in order to sell the products of his company. To travel as quickly as possible, he plans the following strategy.

  • First, he visits city 0.
  • In each of the next steps, he travels to one of the cities he has not visited yet. When taking the decision which city to visit next, the salesman looks at roads from his current city into all unvisited cities, and picks the shortest of these roads. If there are multiple shortest roads, the salesman picks the one of them that leads into the city with the smallest index.
  • He terminates the travel when he has visited all the cities. Note that he does not have to go back to city 0.

The salesman was just about to leave for his journey when he heard a rumor. According to the rumor, one of the roads is just going to be reconstructed. The reconstruction will be done instantly, before the salesman starts to travel. Still, there are two problems. First, the salesman has no idea which one of the roads is the one that's going to be reconstructed. Second, after the reconstruction the new length of the road can be an arbitrary integer between 1 and 9999, inclusive. The salesman is worried how will this change influence his travels in the worst case.

You are given the length of the roads in four separate String[]s. thousands gives the digit in the thousands place of the length of each road, hundreds gives the digit in the hundreds place, tens gives the digit in the tens place, and ones gives the digit in the ones place. In each of these String[]s, the j-th character of the i-th element represents the length of the road from city i to city j. So, for example, if thousands[3][5]='1', hundreds[3][5]='0', tens[3][5]='4', and ones[3][5]='7', the road from city 3 to city 5 has length 1047.

Return the distance the salesman will travel in the worst possible case, given that the length of any single road may change.

Constraints

  • thousands will contain between 2 and 30 elements, inclusive.
  • Each element of thousands will contain N characters, where N is the number of elements in thousands.
  • Each element of thousands will contain only digits ('0' - '9').
  • hundreds, tens and ones will each contain N elements.
  • Each element of hundreds, tens and ones will contain N characters.
  • Each element of hundreds, tens and ones will contain only digits ('0' - '9').
  • The i-th character of the i-th element of thousands, hundreds, tens and ones will be '0'.
  • The length of each road represented by thousands, hundreds, tens and ones is strictly positive.
Examples
0)
{"055", "505", "550"}
{"000", "000", "000"}
{"000", "000", "000"}
{"000", "000", "000"}
Returns: 14999

Every pair of two cities is connected by a road with length 5000. The travel length can reach 14999, for example, if the road from 1 to 2 is reconstructed and its new length is 9999.

1)
{"018", "101", "990"}
{"000", "000", "990"}
{"000", "000", "990"}
{"000", "000", "990"}
Returns: 17999

One of the worst situations for the salesman is if the road from 0 to 1 is reconstructed and its new length is 9999. After this change, the salesman's path becomes 0 -> 2 -> 1. The total distance is 8000 + 9999 = 17999.

2)
{"00888", "00999", "00099", "00009", "00000"}
{"00000", "00999", "00099", "00009", "00000"}
{"00000", "10999", "11099", "11109", "11110"}
{"01000", "00999", "00099", "00009", "00000"}
Returns: 37997

The worst possible case is when the length of the road from 0 to 1 is changed to 8000. After this change, the salesman's path becomes 0 -> 1 -> 2 -> 3 -> 4.

3)
{"000000", "000000", "990999", "999099", "999909", "999990"}
{"000000", "000000", "990999", "999099", "999909", "999990"}
{"000000", "000000", "990999", "999099", "999909", "999990"}
{"011111", "101111", "990998", "999099", "999809", "999980"}
Returns: 39994

One of the worst possible cases is when the length of the road from 0 to 1 is changed to 2.

4)
{"00", "00"}
{"00", "00"}
{"00", "00"}
{"01", "10"}
Returns: 9999

Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GreedyTravelingSalesman with a public method int worstDistance(vector<string> thousands, vector<string> hundreds, vector<string> tens, vector<string> ones) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous