HamiltonianTree
TCO19 Round 4 · 2019-04-15 · by misof
Problem Statement
You are given a
The nodes of the tree are numbered from 0 to N-1, for some appropriate N. The nodes are numbered in order of being discovered by the traversal, with 0 being the root.
Use the given seed to generate a pseudorandom sequence:
- a[0] = seed (this value will remain unused)
- for each i >= 1: a[i] = (a[i-1] * 1103515245 + 12345) modulo 2^31
The edges of the tree can be traversed in either direction. For each i between 1 and N-1, inclusive, the cost of traversing the edge between node i and its parent (in either direction) is (a[i] div 2^21).
The leaves of the tree can be ordered from left to right. This is a cyclic order, i.e., the leftmost and the rightmost leaf are also considered adjacent in this order. In addition to traveling along the edges of the tree, you are also able to jump from any leaf to one of its two neighbors in this cyclic order. You may make as many of these jumps as you want. The cost of each jump is jumpCost.
You want to visit each node exactly once and return to where you started -- i.e., you want to traverse some Hamiltonian cycle. Suppose we order all possible Hamiltonian cycles by their total cost (starting with smallest) and break ties lexicographically. Determine and return the sequence of nodes visited by the index-th Hamiltonian cycle in this order.
The numbering starts from 1.
I.e., for index = 1 you are supposed to return the lexicographically smallest among all cheapest Hamiltonian cycles.
If there is no Hamiltonian cycle for the given index, return an empty
Notes
- If the Hamiltonian cycle we seek exists, the return value should contain exactly N values. Do not append the starting node twice.
- Two Hamiltonian cycles are distinct if they would produce distinct outputs.
Constraints
- N will be between 3 and 250, inclusive.
- dfs will contain 2*(N-1) characters.
- Each character in dfs will be 'D' or 'U'.
- dfs will be a valid traversal of a tree with the properties given in the problem statement.
- seed will be between 0 and 2^31 - 1, inclusive.
- jumpCost will be between 0 and 1023, inclusive.
- index will be between 1 and 10^9, inclusive.
"DUDU"
47
500
3
Returns: {1, 0, 2 }
This is the smallest valid tree. The edge between 0 and 1 has traversal cost 155 and the edge between 0 and 2 has traversal cost 125. Each of the 3! = 6 permutations of nodes is valid and has the same total cost of traversing. Thus, output for index = 3 is the third smallest permutation of {0, 1, 2}.
"DUDU"
47
500
7
Returns: { }
A tree with 3 nodes can have at most 3! = 6 different Hamiltonian cycles.
"DUDUDUDU"
47
500
3
Returns: {1, 0, 4, 3, 2 }
This tree has root = 0 with four children labeled 1, 2, 3, 4 from left to right. The costs of traversing the corresponding edges are {155, 125, 496, 76}. The cheapest way to traverse this tree has total cost 1731. The lexicographically smallest permutation that corresponds to this cost is {0, 1, 2, 3, 4}, the second smallest is {0, 4, 3, 2, 1}, and the third smallest is {1, 0, 4, 3, 2}.
"DUDUDUDU"
47
500
17
Returns: {3, 2, 0, 1, 4 }
"DDDUDUUDUUDUDUDDUDUU"
4747
10
45
Returns: {0, 1, 5, 4, 2, 3, 10, 8, 9, 7, 6 }
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HamiltonianTree with a public method vector<int> construct(string dfs, int seed, int jumpCost, int index) · 86 test cases · 2 s / 256 MB per case