PROBLEM STATEMENT
Social networks have become an integral part of our lives, and Manao is no exception. Back in the
times when Facebook had no news feed, Manao was spending much of his time traversing his friends'
profiles. As you might know, a profile is a page which contains various information about the
user. It also shows some subset of his friends. To be more precise, if a user has less than K
friends, the page shows them all and if not, then only K friends are shown. The subset of K
friends is chosen from the set of all friends every time somebody visits the profile, and all
subsets have equal probability of being chosen.
Manao liked to perform tours of his friends' profiles. He started the tour at his profile and
clicked on one of the friends visible on his page, thus moving to that friend's profile. From
there, he again chose one of his friends from those visible on that page and moved to that
person's profile, and so on. Manao never visited the profiles of people who were not his friends
and never clicked on any of his friends' profiles twice. The tour was finished when he was not
able to proceed because no unvisited profiles of his friends were visible. If Manao visited
profiles of all his friends during the tour, it is considered to be completed, otherwise the tour
is ruined.
Manao lives in Manglisi and there are a total of N people from Manglisi registered at Facebook
(including Manao). We shall number them from 1 to N, where Manao is number 1. It is known that all
friends of each person from Manglisi also live in Manglisi. You are given a vector
friends containing N elements, where the i-th element (1-based) is a space-separated list of
friends of the i-th person. Manao knows the list of friends of everybody in advance. Return the
probability that Manao performs a complete tour if he behaves optimally, i.e., in such a way that
this probability is maximized.
DEFINITION
Class:FriendTour
Method:tourProbability
Parameters:vector , int
Returns:double
Method signature:double tourProbability(vector friends, int K)
NOTES
-The returned value must have an absolute or relative error less than 1e-9.
CONSTRAINTS
-friends will contain between 2 and 36 elements, inclusive.
-Each element of friends will contain between 1 and 36 characters, inclusive.
-Each element of friends will contain a space-separated list of distinct integers without leading
zeros.
-Each of the numbers in friends will be between 1 and N, inclusive. Number i will never occur in
element i (1-based) of friends.
-If number i is present in friends[j], then number j will be present in friends[i] (both indices
are 1-based).
-K will be between 1 and 36, inclusive.
EXAMPLES
0)
{"2 3 4",
"1 3 4",
"1 2 4",
"1 2 3"}
1
Returns: 0.2222222222222222
Manao has three friends, who are all also friends with each other. Every time a profile is viewed,
only one friend is shown. No matter which friend appears on Manao's profile first, the probability
that Manao will continue his tour from that friend's profile is 2/3 and the probability that Manao
will visit the last friend left is 1/3, which results in a total of 2/9.
1)
{"2 3 4",
"1 3 4",
"1 2 4",
"1 2 3"}
2
Returns: 0.6666666666666666
This time, two friends are shown on each profile. No matter how Manao chooses between unvisited
profiles, there is a 1/3 probability that he won't be able to complete the tour.
2)
{"3 2 4",
"3 5 1",
"5 2 1 4",
"3 1 5",
"3 2 4"}
2
Returns: 0.3333333333333333
Note that the friend numbers in the lists don't have to follow in increasing order. Also, unlike
the previous examples, this time the outcome depends on Manao's strategy.
3)
{"3 2 4",
"3 5 1",
"5 2 1 4",
"3 1 5 6",
"3 2 4",
"4"}
2
Returns: 0.3055555555555556
4)
{"6 5 4 2",
"1 6 3 5",
"5 4 2",
"3 1 5",
"2 4 3 1 6",
"1 2 5"}
3
Returns: 0.73125
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.