MinimumCuts
2015 TCO Parallel 2B · 2015-04-08 · by zxqfl
Problem Statement
Alice is playing a game with Bob.
The game is played on a binary tree of N vertices, which are numbered from 0 to N-1. (In this problem, a binary tree is any rooted tree in which each vertex has at most two children.) For each integer i such that 0 <= i < N-1, an undirected edge with cost cost[i] connects vertex parent[i] and vertex i+1. If there is no value of i such that parent[i] = X, then vertex X is called a leaf. Bob has a token which starts on vertex 0. At each step of the game:
- Bob selects an edge which is adjacent to his token.
- Alice may choose to permanently remove the edge and pay the cost associated with it. If she does so, the move is cancelled.
- Otherwise, Bob moves the token along the edge.
Bob cannot use any edge more than twice (once in each direction). If Bobâs token ever reaches a leaf, Alice loses the game. Alice wins if Bob has no valid moves.
Alice can always win the game. She would like to do so while minimizing the total cost she pays, while Bob wants to maximize it. Assuming both players play optimally, return the cost paid by Alice.
Constraints
- N will be between 2 and 100, inclusive.
- parent and cost will contain exactly N-1 elements.
- For each valid i, parent[i] will be between 0 and i, inclusive.
- For each valid i, cost[i] will be between 1 and 10000, inclusive.
- The edges will form a binary tree rooted at vertex 0. For each X, there are at most 2 values of i such that parent[i] = X.
{0, 1}
{3, 5}
Returns: 3
Alice must stop Bob from reaching vertex 2, since it is a leaf, so she must cut edge 0-1 or edge 1-2. The cheapest option, with cost 3, is to cut edge 0-1.
{0, 0}
{10000, 1}
Returns: 10001
Alice must cut both edges, since vertex 1 and vertex 2 are both leaves.
{0, 0, 1, 1, 2, 2}
{4, 5, 1, 2, 3, 3}
Returns: 8
The optimal solution is to cut edges 0-2 (cost 5), 1-3 (cost 1), and 1-4 (cost 2).
{0, 0, 1, 1, 2, 2, 3, 4, 5, 6}
{9, 9, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: 2
{0, 1, 0, 3, 3, 5}
{5, 5, 10000, 100, 1, 1}
Returns: 105
The answer would be 106 if Bob could use edge 0-3 more than twice.
Submissions are judged against all 82 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MinimumCuts with a public method int costPaid(vector<int> parent, vector<int> cost) · 82 test cases · 2 s / 256 MB per case