Connection Status:
Competition Arena > TokenTree

TokenTree

TCO 22 Semi 2 · 2022-11-17 · by misof

TCO 22 Semi 2 · 2022-11-17 · by misof · Graph Theory, Greedy
Class Name: TokenTree
Return Type: int
Method Name: maxTokens
Arg Types: (int, int, vector<int>, int, int)
Problem Statement

Problem Statement

You have a tree. Its vertices are numbered from 0 to N-1.

You want to place some tokens onto the vertices of the tree. Each vertex may contain at most one token. Each simple path may contain at most K tokens. Maximize the number of tokens on the tree and return that maximum.


For each i between 0 and N-2, inclusive, the tree contains an undirected edge between vertices (i+1) and P[i].

For all i we will have P[i] < (i+1), which ensures that the collection of N-1 edges is a tree.


In order to keep the input small, the tree is (mostly) pseudorandom. Please use the pseudocode below to generate its array P. 


state = seed
L = length(Pprefix)

for i = 0 to L-1:
    P[i] = Pprefix[i]

for i = L to N-2:
    lo = max(0, i-D+1)
    state = (state * 1103515245 + 12345) modulo 2^31
    P[i] = lo + (state modulo (i-lo+1))

Notes

  • The reference solution does not depend on the input being pseudorandom.
  • The parameter D used in the pseudocode influences the shape of the resulting tree.

Constraints

  • N will be between 1 and 500,000, inclusive.
  • K will be between 1 and N, inclusive.
  • Pprefix will contain between 0 and min(N-1, 200) elements.
  • For each i, Pprefix[i] will be between 0 and i, inclusive.
  • D will be between 1 and N, inclusive.
  • seed will be between 0 and 2^31 - 1, inclusive.
Examples
0)
8
4
{}
1
47
Returns: 4

Regardless of the random seed, the choice D = 1 ensures that the generated tree will be a path: you will get P = {0, 1, 2, 3, 4, 5, 6} and thus the tree edges are 0-1, 1-2, ..., 6-7. Clearly, you can place up to four tokens anywhere you like and you will have a valid solution. You cannot place more than four tokens because then the path that is the whole tree would contain too many tokens.

1)
8
2
{0, 0, 0, 0, 0, 0, 0}
8
42
Returns: 7

We are given the entire array P in Pprefix. The tree is a star with 0 in the center. No path may contain more than two tokens. The optimal solution is to place a token into each of the vertices 1-7.

2)
8
7
{0, 0, 0, 0, 0, 0, 0}
8
23236
Returns: 8

Same graph as in the previous example but now each path may contain up to 7 tokens. The optimal solution is to simply place a token everywhere, so the total number of tokens is N = 8.

3)
10
4
{0, 0, 1}
4
12345
Returns: 7

Here you should generate P = {0, 0, 1, 2, 4, 2, 4, 6, 8}. The generated tree is depicted below. 3 --- 1 --- 0 --- 2 --- 6 --- 8 --- 9 | | 5 --- 4 --- 7 One optimal solution is to place seven tokens at vertices 0, 1, 4, 5, 6, 7, and 9.

4)
1234
1
{}
47
23325
Returns: 1

If no simple path may contain more than one token, there can only be at most one token on the entire tree. We can place one token anywhere we like, all those solutions are valid and therefore optimal.

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

Coding Area

Language: C++17 · define a public class TokenTree with a public method int maxTokens(int N, int K, vector<int> Pprefix, int D, int seed) · 90 test cases · 2 s / 256 MB per case

Submitting as anonymous