LotteryTree
SRM 609 · 2013-12-22 · by semiexp
SRM 609 · 2013-12-22 · by semiexp · Brute Force, Math
Problem Statement
Problem Statement
You held a lottery and P people participated in it.
Now you want to determine who won the lottery prize.
You have decided to choose the winner using a rooted tree. You are going to make a lottery with the tree as follows:int P and a int[] tree that describes the tree you will use.
The tree has N nodes, conveniently numbered 0 through N-1.
Node 0 is the root of the tree.
For each other node, the number of its parent is smaller than its own number.
More precisely, for each i between 1 and N-1, inclusive, tree[i-1] is the parent of node i.
You want to make the lottery fair.
That is, you want to guarantee that each of the participants will have the same probability to win the lottery.
To do that, you can choose how to draw the tree, and how to assign integers to its leaves (while following the above procedure).
Return "YES" (quotes for clarity) if you can make the lottery fair and "NO" otherwise.
You have decided to choose the winner using a rooted tree. You are going to make a lottery with the tree as follows:
- The participants are conveniently numbered from 1 to P, inclusive.
- First, you draw the tree onto a rectangular board in such a way that the tree satisfies the following conditions:
- Each node of the tree corresponds to a small circle on the board. The circles are so small that you can ignore their size.
- Each edge of the tree corresponds to a line segment connecting two circles. No two edges are allowed to intersect.
- The root node must be drawn on the top edge of the board.
- For each node, all edges to its children must be going downwards. (In other words, the parent of a node must always be drawn above the node.)
- All of the leaves must be drawn on the bottom edge of the board.
- Next, you split the bottom edge of the board into P segments in such a way that each leaf belongs to exactly one segment. For each segment, you choose a different integer between 1 and P, inclusive, and write that integer into each of the leaves that belong to that segment.
- Now, you will repeat the following process: Find an empty node X such that you have already written integers into all of its children. If there are multiple nodes with this property, choose one uniformly at random. Choose a child of X uniformly at random, and copy the integer written in the chosen child into X. The process terminates once the root node contains an integer.
Constraints
- tree will have between 2 and 100 elements, inclusive.
- For each i, element i (0-based index) of tree will be between 0 and i, inclusive.
- P will be between 2 and 100, inclusive.
- Each node that is not a leaf will have at least 2 children.
Examples
0)
{0, 0, 0}
3
Returns: "YES"
One of the ways to draw the tree is as follows:
1)
{0, 0, 0, 1, 1, 2, 2, 3, 3}
2
Returns: "YES"
One of the ways to draw the tree is as follows: Note that you cannot assign integers to the leaves as follows:
2)
{0, 0, 1, 1, 2, 2, 4, 4, 4}
3
Returns: "NO"
You would be able to make this tree fair if you were allowed to assign integers to leaves arbitrarily. However, given the additional restriction that each integer must be assigned to a consecutive segment of leaves, making this tree fair is not possible.
3)
{0, 0, 1, 1, 1, 3, 3, 3}
3
Returns: "NO"
4)
{0, 0, 0, 3, 0, 0, 3, 6, 3, 1, 0, 2, 0, 4, 6, 15, 1, 15, 11, 11, 1, 4, 11, 2, 11, 2, 6}
6
Returns: "YES"
Submissions are judged against all 254 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LotteryTree with a public method string isFairTree(vector<int> tree, int P) · 254 test cases · 2 s / 256 MB per case