TopCoder problem "Party" used in SRM 263 (Division II Level One)

Problem Statement

    You are at a party where no one knows anyone else's name. Each time two people shake hands, they introduce themselves to each other, and share with the other all the names they've learned at the party so far. You will be given an int n, the number of people at the party. You will also be given a int[] personA and a int[] personB, containing the zero-based indices of the people who shook hands with each other, in chronological order. Elements of personA and personB with equal indices describe the same handshake. You should return the average number of names that each person at the party has learned, not including his or her own name.


Parameters:int, int[], int[]
Method signature:double averageNames(int n, int[] personA, int[] personB)
(be sure your method is public)


-n will be between 2 and 100, inclusive.
-personA and personB will contain between 1 and 50 elements, inclusive.
-personA and personB will contain the same number of elements.
-Each element of personA and personB will be between 0 and n-1, inclusive.
-personA[k] will be unequal to personB[k] for all valid k (no one will shake hands with themselves).


Returns: 2.25

First person 0 shakes hands with person 1, and they learn each other's names. Then person 1 and person 2 shake hands, introduce each other and talk about person 0. Finally, person 2 shakes hands with person 3, introduce themselves and discuss persons 0 and 1.

Person 0 knows one other party-goer, person 1 knows two, and persons 2 and 3 both know about all three other people. Therefore, you should return (1+2+3+3) / 4 = 2.25.

Returns: 4.0

Halfway through the party, everyone has introduced themselves to person 0 (and vice versa). Person 0 spends the remaining half of the party going back down the list and sharing everyone's names with everybody else. By the end of the party, each partygoer knows the names of all four other people.

Returns: 0.02

Only two people talk to each other during the entire party; the other 98 people leave without having learned anyone else's name.

{14, 14, 16, 4, 14, 16, 2, 16, 8, 15, 17, 17, 3, 3, 19, 17, 20, 4, 24, 8}
{16, 2, 23, 16, 11, 8, 5, 19, 15, 20, 19, 18, 14, 12, 22, 9, 0, 7, 23, 10}
Returns: 4.44

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force, Simulation