Treestrat
SRM 670 · 2015-08-31 · by subscriber
Problem Statement
Two players are playing a game with some tokens on a tree.
Player A has one or more red tokens. Player B has one or more blue tokens. Initially, each vertex of the tree is either empty or contains exactly one token (either a red one or a blue one, not both). During the game there can be arbitrarily many tokens of each color in each vertex.
You are given the description of the initial state of the game.
More precisely, you are given the
The game is played in rounds. Each round consists of two phases.
In the first phase player A may move some of his tokens, and in the second phase player B may move some of her tokens. More precisely, the current player always examines all of their tokens, and for each of them the player either decides to keep it in its current vertex, or decides to move it to one of the adjacent vertices.
Player B wins if after some round there is a vertex that contains both a red and a blue token. (There can even be multiple red or blue tokens in that vertex.)
Player B wants to win in as few rounds as possible. Player A wants the game to go for as many rounds as possible. Assume that both players play the game optimally.
Compute and return the number of rounds the game will take.
Note that it can be shown that the answer is always finite: player B always has a winning strategy. Also note that you are supposed to return the number of rounds, not the total number of phases.
Constraints
- tree will contain n - 1 element.
- n will be between 2 and 50, inclusive.
- i-th elements in tree will be between 0 and i, inclusive.
- A will contain between 1 and 50 elements, inclusive.
- B will contain between 1 and 50 elements, inclusive.
- Each element in A and B will be between 0 and n - 1, inclusive.
- No element will occur more than once in the concatenation of A and B.
{0}
{0}
{1}
Returns: 1
This is a tree with a single edge 0-1. Initially there is a red token in vertex 0 and a blue token in vertex 1. Regardless of where player A moves the red token, player B can move the blue token to the same vertex and win.
{0,1}
{1}
{2}
Returns: 2
This tree is a line that consists of two edges: 0-1 and 1-2. We start with a red token on vertex 1 and a blue token on vertex 2. Player A's optimal strategy is to start by moving his token into vertex 0. Player B will then move her token into vertex 1. In the second round player B will then win the game in the same way as in Example 0.
{0,0,0,3,4}
{2}
{1}
Returns: 2
{0,0,0,3,4,2}
{1}
{6}
Returns: 5
{0,0,0,3,4,2}
{1}
{6,5}
Returns: 3
Submissions are judged against all 133 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Treestrat with a public method int roundcnt(vector<int> tree, vector<int> A, vector<int> B) · 133 test cases · 2 s / 256 MB per case