Connection Status:
Competition Arena > Party

Party

SRM 263 · 2005-09-14 · by LunaticFringe

SRM 263 · 2005-09-14 · by LunaticFringe · Brute Force, Simulation
Class Name: Party
Return Type: double
Method Name: averageNames
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

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.

Constraints

  • 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).
Examples
0)
4
{0,1,2}
{1,2,3}
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.

1)
5
{0,0,0,0,0,0,0}
{1,2,3,4,3,2,1}
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.

2)
100
{52,19,52,19}
{19,52,19,52}
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.

3)
97
{38,56,77,88,72,21,26,69,2,25,47,85,36,52,28,73,96,86,89,61,33,16,76,57,55,95,82,78,31,92,3,70,74,35,30,50,49,11,94,21,76,17,67,45,68,12,52,55,55,33}
{89,34,52,26,86,11,59,81,14,32,50,11,1,33,20,17,82,22,4,70,5,24,56,6,88,12,58,55,66,61,81,89,43,37,56,72,59,29,73,74,21,56,60,78,34,37,63,82,42,40}
Returns: 1.6391752577319587
4)
20
{13,3,9,16,10,11,9,8,19,1,5,7,6,17,17,19,14,5,9,8}
{5,14,16,12,11,19,17,6,16,10,12,0,16,5,3,5,12,4,4,4}
Returns: 4.85

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

Coding Area

Language: C++17 · define a public class Party with a public method double averageNames(int n, vector<int> personA, vector<int> personB) · 110 test cases · 2 s / 256 MB per case

Submitting as anonymous