Connection Status:
Competition Arena > GameWithTree

GameWithTree

TCO13 Semifinal 1 · 2013-02-19 · by K.A.D.R

TCO13 Semifinal 1 · 2013-02-19 · by K.A.D.R · Dynamic Programming, Graph Theory
Class Name: GameWithTree
Return Type: String
Method Name: winner
Arg Types: (vector<int>, string)
Problem Statement

Problem Statement

Little Petya likes rooted trees a lot. Recently he has received one as a gift from his mother. The only thing Petya likes more than rooted trees is playing with little Masha. The children painted each node of Petya's new tree either black or white. The tree is represented by the int[] parent. Let N denote the number of nodes in the tree. The nodes are numbered 0 through N-1. Node 0 is considered to be the root of the tree. Then for each i between 0 and N-2, inclusive, the tree contains an edge between nodes (i+1) and parent[i]. (Note that parent[i] may sometimes be greater than i+1.) The colors of nodes are given in the String color that consists of characters 'W' and 'B'. If the i-th character (0-based index) of color is 'W', then the i-th node is colored white, otherwise it's colored black.


The children decided to play a game with this tree. In the game Petya and Masha take alternating turns, Masha plays first. On his or her turn, the current player selects a white node, along with any subset of its descendants. (The subset can be arbitrary, possibly disconnected or even empty.) The player then toggles the color of all selected vertices: black nodes become white and vice versa. A player who can't make a turn loses the game. You goal is to determine who will be the winner assuming that both kids play optimally. Return "Masha" (without quotes) if Masha wins, otherwise return "Petya".

Notes

  • Node A is called a descendant of the node B if either B is a parent of A or a parent of A is descendant of the node B.

Constraints

  • parent will contain N-1 elements.
  • Each element of parent will be between 0 and N-1, inclusive.
  • color will contain N characters.
  • N will be between 2 and 50, inclusive.
  • Each character of color will be either 'B' or 'W'.
  • It's guaranteed that the graph described by parent is a rooted tree with root 0.
Examples
0)
{0}
"WW"
Returns: "Masha"

As the root is white, Masha may select the root together with any subset of other vertices in the tree. The optimal strategy for her is to select and toggle both vertices.

1)
{0,0}
"BWW"
Returns: "Petya"

Here the root is black. Masha must select and toggle exactly one of the leaves on her first turn. Then, Petya will select the other leaf and win the game.

2)
{0,1,2,3}
"BBBBB"
Returns: "Petya"

In this test case there are no white nodes, so Masha can't even make the first move.

3)
{5,5,6,6,0,0}
"BBWWBWW"
Returns: "Petya"

Here we have a black root that has two children with identical subtrees. Petya can mirror Masha's moves. This will guarantee him a victory.

4)
{5,5,6,6,0,0}
"BWWBBBW"
Returns: "Masha"

One optimal strategy for Masha: In the first turn, Masha will select and toggle only the node 6. Thus, only two white nodes will remain, both of them will be leaves. After Petya toggles one of them, Masha will toggle the other one and win. (Note that there are also other winning strategies for Masha in this situation.)

Submissions are judged against all 115 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GameWithTree with a public method string winner(vector<int> parent, string color) · 115 test cases · 2 s / 256 MB per case

Submitting as anonymous