Connection Status:
Competition Arena > PrinceXToastbook

PrinceXToastbook

SRM 537 · 2011-11-22 · by dolphinigle

SRM 537 · 2011-11-22 · by dolphinigle · Graph Theory
Class Name: PrinceXToastbook
Return Type: double
Method Name: eat
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Prince Gogo is the charming prince of the Kingdom of Ducks, where slimes and ducks live in peace and harmony.

Today, Prince Gogo purchased N toastbooks, numbered 0 through N-1. Each toastbook contains some knowledge and grants it to the person who eats it. It is known that no two toastbooks contain the same knowledge.

Initially, Gogo doesn't know any of the knowledge inside the toastbooks. He intends to eat them all and gain as many pieces of knowledge as possible. Furthermore, some of the books require a specific piece of knowledge in order to understand its knowledge. This will be given as a int[] prerequisite. If there is no required knowledge to understand the toastbook number i, prerequisite[i] will be -1. Otherwise, prerequisite[i] will be the number of the toastbook that contains the knowledge necessary to understand book i. If Gogo eats some book x without having the required knowledge, he will not gain the knowledge inside the book, even if he later gains the knowledge from the book prerequisite[x].

Unfortunately, Gogo forgot to number the toastbooks when he purchased them. Hence, he is forced to eat all N toastbooks in a random order. Return the expected number of toastbooks that Gogo will understand.

Notes

  • The expected value of a random variable can be imagined as the average value of very many independent experiments.
  • The returned value must have an absolute or relative error less than 10^-9.

Constraints

  • prerequisite will contain between 2 and 50 elements, inclusive.
  • Each element of prerequisite will be between -1 and N-1, inclusive, where N is the number of elements in prerequisite.
  • For all i, prerequisite[i] will not be i.
Examples
0)
{-1, 0}
Returns: 1.5

There are only two possible orders. If Gogo eats book 0 first, he gains the knowledge in both books. If Gogo eats book 1 first, he lacks the required knowledge to understand the book 1 when he read it. Hence, he will only gain the knowledge in book 0. Therefore, the expected number of books that Gogo will understand is the average of the two, which is 1.5.

1)
{-1, 0, 1}
Returns: 1.6666666666666667

There are 6 possible orders. The number of books understood is as follows: 0, 1, 2: 3 0, 2, 1: 2 1, 0, 2: 1 1, 2, 0: 1 2, 0, 1: 2 2, 1, 0: 1 Hence, the expected number of books that Gogo will understand is their average, which is (3+2+1+1+2+1)/6 = 10/6.

2)
{1, -1, 1}
Returns: 2.0
3)
{1, 0}
Returns: 0.0

Each book has the other book as a prerequisite. Gogo will not be able to understand either one, regardless of the order in which he eats them.

4)
{-1, -1}
Returns: 2.0

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

Coding Area

Language: C++17 · define a public class PrinceXToastbook with a public method double eat(vector<int> prerequisite) · 167 test cases · 2 s / 256 MB per case

Submitting as anonymous