YetAnotherHamiltonianPath | Topcoder Archive

Problem Statement

A Hamiltonian path in an undirected graph with N vertices is a sequence of vertices A₁, A₂, ..., A_N such that all A_i are pairwise distinct and for each i (1 &lt i &le N), there is an edge between vertices A_i-1 and A_i. A path starts at vertex A₁ and visits each vertex of the sequence in order, ending at vertex A_N. 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.

Definition

Class:: YetAnotherHamiltonianPath
Method:: leastCost
Parameters:: String[]
Returns:: int
Method signature:: int leastCost(String[] label)
(be sure your method is public)

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

```
{"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.
```
{"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.
```
{"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".

{"canada", "cyprus", "croatia", "colombia", "chile", "china", "cameroon"}

Returns: 509

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)2024, Topcoder, Inc. All rights reserved.