Connection Status:
Competition Arena > FriendTour

FriendTour

SRM 476 · 2009-12-03 · by gojira_tc

SRM 476 · 2009-12-03 · by gojira_tc · Dynamic Programming, Greedy, Math
Class Name: FriendTour
Return Type: double
Method Name: tourProbability
Arg Types: (vector<string>, int)
Problem Statement

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 String[] 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.

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 4", "1 4", "4", "1 2 3"}
2
Returns: 1.0
1)
{"2","1"}
2
Returns: 1.0
2)
{"2","1"}
1
Returns: 1.0
3)
{"2 7", "1 3 5 7", "2 4 6 7", "3 5", "2 4 7", "3", "1 2 3 5"}
3
Returns: 0.75
4)
{"5 6 7 9", "5 7 8 9 10", "4 5 7 8 9", "3 5", "1 2 3 4 9", "1 7 9 10", "1 2 3 6", "2 3", "1 2 3 5 6", "2 6"}
2
Returns: 0.07666666666666667
7)
{"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.

8)
{"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.

9)
{"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.

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

Coding Area

Language: C++17 · define a public class FriendTour with a public method double tourProbability(vector<string> friends, int K) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous