TokenTree | Topcoder Archive

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))

Definition

Class:: TokenTree
Method:: maxTokens
Parameters:: int, int, int[], int, int
Returns:: int
Method signature:: int maxTokens(int N, int K, int[] Pprefix, int D, int seed)
(be sure your method is public)

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

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

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.