FoxAndGo4
2016 TCO Algo 3A · 2016-03-24 · by cgy4ever
Problem Statement
Sometimes the endgame of Go can be modeled as a simple game on a tree. This game is described below.
Given is a tree with n+1 nodes. The nodes are numbered 0 through n, inclusive. You are given the description of this tree: a
At the beginning of the game there is a black stone on node 0. All other nodes are empty. Ciel plays with black stones, Snuke plays white. The players take alternating turns. Ciel goes first.
Whenever it is Ciel's turn, she must place one new black stone onto an empty node that is adjacent to a node that has a black stone.
If there are multiple valid moves, she may choose any one of them.
If there are no valid moves, the whole game ends.
Whenever it is Snuke's turn, he can either pass (do nothing) or he can choose any one empty node and place a white stone on it.
The result of the game is the number of empty nodes when the game ends. Ciel wants to minimize the result, Snuke wants to maximize it. Assume that both players play the game optimally.
Compute and return the result of the game.
Constraints
- p will contain between 1 and 50 elements, inclusive.
- For each valid i, 0 <= p[i] <= i.
{0,1,2,3,4,5}
Returns: 4
This tree is a line: 0-1-2-3-4-5-6. The game will play out as follows: Ciel has only one valid move: she must place a black stone onto node 1. Snuke now has multiple options: he may pass, or he may place a white stone onto one of the nodes 2, 3, 4, 5, 6. Clearly, the optimal move is to place a white stone onto node 2. Ciel now has no valid moves, so the game ends. There are 4 empty nodes, hence the result of the game is 4.
{0,0,2,0,4,5}
Returns: 1
The tree looks as follows: 1 | 0--2--3 | 4--5--6 Here is one possible game in which both players play optimally: Ciel puts a black stone on node 4. Snuke puts a white stone on node 2. Ciel puts a black stone on node 5. Snuke puts a white stone on node 1. Ciel puts a black stone on node 6. Snuke passes. Ciel has no valid moves so the game ends. There is only one empty node (node 3), so the result is 1.
{0,1,2,0,4,5,0,7,8}
Returns: 3
{0,0,1,1,2,2,3,3,4,4,5,5,6,6}
Returns: 8
{0}
Returns: 0
Submissions are judged against all 177 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FoxAndGo4 with a public method int score(vector<int> p) · 177 test cases · 2 s / 256 MB per case