TreeTokens
2021 Regional 1 · 2021-04-13 · by misof
Problem Statement
Given is an undirected tree with N vertices. As usual, vertices are numbered 0 to N-1.
We are going to place some tokens into the vertices of the tree. All tokens are identical. Arbitrarily many tokens can be placed into the same vertex.
Once we are done, our opponent will have the option to move the tokens. In order to make a move, the opponent must always do the following:
- the opponent has to select two tokens that are in the same vertex of the tree,
- they have to remove one of them (as payment for the move)
- then, they may move the other token along an edge of the tree to a different vertex.
The opponent may make as many moves as they like, anywhere where moves can be performed. Each token may be moved arbitrarily many times.
We want to make sure that vertex G remains empty, regardless of what our opponent does. What is the maximum total number of tokens we can place onto the tree? Compute this value and return the remainder it gives modulo 1,000,000,007.
In order to keep the input small, the tree is generated pseudorandomly using the following pseudocode:
state = seed
for i = 1 to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
tmp = (state / 1000) modulo L
p = max(0, i-1-tmp)
add a tree edge that connects vertices i and p
Notes
- The reference solution does not depend on the input being pseudorandom.
Constraints
- N will be between 1 and 100,000, inclusive.
- G will be between 0 and N-1, inclusive.
- L will be between 1 and 10^7, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
5 0 1000000 1234567 Returns: 4
The tree consists of the edges 0-1, 0-2, 0-3, and 0-4. We want to prevent our opponent from getting a token onto vertex 0. The best we can do is to place one token onto each of the other four vertices. This way the opponent cannot make any valid move.
5 4 1 1234567 Returns: 15
The tree consists of the edges 0-1, 1-2, 2-3, and 3-4. We want to prevent our opponent from getting a token onto vertex 4. The best we can do is to take 15 tokens and place all of them onto vertex 0. The opponent will be able to do some moves, but they won't be able to get a token onto vertex 4. Regardless of how we distribute 16 (or more) tokens, the opponent will always have a way to get some token onto vertex 4.
4 0 2 4742 Returns: 4
The intermediate values of the variable "state" are 1599137607, 601115508, 1075423389. (Watch out for integer overflows.) The generated tree edges are 1-0, 2-0, and 3-1.
1 0 7 43634 Returns: 0
2 1 5 23623 Returns: 1
7 5 3 47 Returns: 17
Edges: 0-1, 0-2, 0-3, 3-4, 4-5, 3-6.
Submissions are judged against all 32 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TreeTokens with a public method int placeMax(int N, int G, int L, int seed) · 32 test cases · 2 s / 256 MB per case