Connection Status:
Competition Arena > YetAnotherHamiltonianPath

YetAnotherHamiltonianPath

SRM 496 · 2010-11-01 · by gojira_tc

SRM 496 · 2010-11-01 · by gojira_tc · Graph Theory, Greedy, String Manipulation
Class Name: YetAnotherHamiltonianPath
Return Type: int
Method Name: leastCost
Arg Types: (vector<string>)
Problem Statement

Problem Statement

A Hamiltonian path in an undirected graph with N vertices is a sequence of vertices A1, A2, ..., AN such that all Ai are pairwise distinct and for each i (1 &lt i &le N), there is an edge between vertices Ai-1 and Ai. A path starts at vertex A1 and visits each vertex of the sequence in order, ending at vertex AN. The cost of a path is the sum of the weights of the edges connecting the path's consecutive vertices.

You're given a graph where the i-th (0-based) vertex is labeled with String label[i]. There is an edge between each pair of vertices. The cost of the edge between vertices i and j is equal to length^2 (label[i]) + length^2 (label[j]) - length^2 (LCP (label[i], label[j]) ), where "^2" denotes squaring operation, length(X) is the length of string X and LCP(X,Y) is the longest common prefix of strings X and Y.

Return the minimum possible cost of a Hamiltonian path which starts at vertex 0 and ends at vertex 1.

Notes

  • A prefix of string S is a string that can be obtained by removing zero or more contiguous characters from the end of S.
  • The longest common prefix of two strings A and B is the longest possible string which is a prefix of both A and B.

Constraints

  • label will contain between 2 and 50 elements, inclusive.
  • Each element of label will be between 1 and 50 characters long, inclusive.
  • Each element of label will consist of lowercase letters ('a'-'z') only.
Examples
0)
{"home", "school", "pub"}
Returns: 70

The only possible Hamiltonian path from vertex 0 to vertex 1 is 0->2->1. Vertex 0 is labeled "home", and vertex 1 is labeled "pub", so since these two strings have no common prefix, the cost of the edge 0->1 is 4^2+3^2=25. The cost of the edge 2->1 is 45, so the total cost of the path is 70.

1)
{"school", "home", "pub", "stadium"}
Returns: 167

Of the two possible Hamiltonian paths, the cost of the one that visits "stadium" right after "school" is 1 less than the other one's.

2)
{"abcd","aecgh","abef","aecd"}
Returns: 91

The cost matrix of this graph is: -- 40 28 31 40 -- 40 32 28 40 -- 31 31 32 31 -- The optimal path is "abcd"->"abef"->"aecd"->"aecgh".

3)
{"manglisi", "tbilisi"}
Returns: 113
4)
{"a","a"}
Returns: 1

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

Coding Area

Language: C++17 · define a public class YetAnotherHamiltonianPath with a public method int leastCost(vector<string> label) · 133 test cases · 2 s / 256 MB per case

Submitting as anonymous