Hamiltons

TCO20 Round 3A · 2020-04-13 · by misof

TCO20 Round 3A · 2020-04-13 · by misof · Graph Theory, Greedy, Math

Show categories

Class Name: Hamiltons

Return Type: int[]

Method Name: construct

Arg Types: (int, int)

Problem Statement

In this problem you are given the ints N >= 6 and L >= 10. We will consider complete undirected graphs with N vertices in which each edge is labeled with a positive integer between 1 and L, inclusive. Below, "a graph" denotes a graph with these properties.

Maru and Vlado were given a standard programming homework: given a graph, find the cost of the cheapest Hamiltonian path.

Maru has implemented her solution properly. Vlado was lazy: He realized that he had recently implemented a program that constructs one of the cheapest Hamiltonian cycles in the given graph. Given this new homework, he now thought: "That's easy! I'll just construct the cycle and then I'll throw away the most expensive edge and I'm done." Your task is to show that this lazy approach does not have to work.

We will now introduce several definitions.

Let Maru(G) be the cost of the optimal Hamiltonian path for G.
Let Vlado(G) be the smallest cost of a Hamiltonian path Vlado's algorithm might return for G. That is, if G contains multiple cheapest Hamiltonian cycles, assume that Vlado's algorithm will always get lucky and pick the one among them that produces the cheapest Hamiltonian path.

Construct any graph G such that Vlado(G) - Maru(G) >= L/2.

Return a int[] that contains the upper triangular half of the distance matrix of your G in row major order. That is, if the vertices of your graph G are labeled starting from 0 and e(i,j) is the weight of edge i-j, return { e(0,1), e(0,2), ..., e(0,N-1), e(1,2), e(1,3), ..., e(N-2,N-1) }.

Notes

For the given constraints a solution always exists.
You are not required to optimize the value Vlado(G) minus Maru(G). Any graph that matches the requirements listed in the statement will be accepted.

Constraints

N will be between 6 and 14, inclusive.
L will be between 10 and 1000, inclusive.

Examples

6
20
Returns: {20, 6, 5, 16, 20, 1, 3, 6, 17, 8, 1, 9, 14, 14, 6 }

The distance matrix of the returned graph G: 0 20 6 5 16 20 20 0 1 3 6 17 6 1 0 8 1 9 5 3 8 0 14 14 16 6 1 14 0 6 20 17 9 14 6 0 The shortest Hamiltonian path is the path 0-3-1-2-4-5 with total length Maru(G) = 5 + 3 + 1 + 1 + 6 = 16. The shortest Hamiltonian cycle is the cycle 0-3-1-4-5-2(-0) with total length 5 + 3 + 6 + 6 + 9 + 6 = 35. Hence, Vlado(G) = 35 - 9 = 26. The difference between Vlado(G) and Maru(G) is precisely 10 = L/2.

6
1000
Returns: {174, 325, 60, 839, 248, 437, 398, 965, 806, 658, 985, 969, 319, 100, 149 }

The distance matrix of the returned graph G: 0 174 325 60 839 248 174 0 437 398 965 806 325 437 0 658 985 969 60 398 658 0 319 100 839 965 985 319 0 149 248 806 969 100 149 0 The shortest Hamiltonian path has length 920. This is the path 2-1-0-3-5-4 with edge lengths 437, 174, 60, 100, 149. The unique shortest Hamiltonian cycle is the cycle 0-2-1-3-4-5-0. Its edge lengths are 325, 437, 398, 319, 149, 248. Thus, Vlado will discard the longest edge (2-1, length 437) and obtain the Hamiltonian path 1-3-4-5-0-2 with total length 1439. The difference 1439 - 920 = 519 is large enough: L/2 is only 500.

11
11
Returns: {1, 11, 11, 11, 11, 11, 11, 11, 4, 11, 1, 11, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 4, 1, 11, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 11, 1, 11, 11, 11, 11, 1, 11, 11, 11, 1, 11, 11, 1, 11, 1 }

7
12
Returns: {1, 12, 12, 12, 5, 12, 1, 12, 12, 12, 4, 1, 12, 12, 4, 1, 12, 12, 1, 12, 1 }

12
12
Returns: {1, 12, 12, 12, 12, 12, 12, 12, 12, 5, 12, 1, 12, 12, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 12, 4, 1, 12, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12, 1, 12, 12, 12, 1, 12, 12, 1, 12, 1 }

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

Coding Area

Language: C++17 · define a public class Hamiltons with a public method vector<int> construct(int N, int L) · 100 test cases · 2 s / 256 MB per case