PROBLEM STATEMENT
It's the annual Clover Ball at Princeton University. Many people came here to
dance. You are given a String[] representing the preferences of the dancers in
attendence. Each String consists of several names of dancers, for example,
"ALICE BOB DAVID". The first person named in the String is willing to dance
with everyone else named in the String (but not necessarily vice versa). In the
example above, ALICE is willing to dance with BOB or DAVID. When the music for
one dance is playing the people who are willing to dance with each other create
pairs and dance. We are interested in counting in how many different ways
people can arrange themselves in pairs for dancing in such a way that no two
dances are danced with exactly the same set of pairs.
Your task is, given a String[] describing the wishes of all the dancers, return
the maximum number of dances that can be danced such that there are no two
dances with exactly the same set of pairs and such that each dancing person in
each dance dances with a desirable partner.
In more detail, assume that:
- no two people have the same name
- people do not switch partners in the middle of a dance
- dances are danced only in pairs
- same gender pairs are allowed
- the dance in which nobody dances doesn't count
- each element of the input contains at least two names (separated by white
space). The first name belongs to the person whose wishes are described in this
String. All other names belong to those people with whom the first named person
is willing to dance.
NOTE
If multiple Strings define the preferences of a given person, then that person
is willing to dance with all of the people mentioned in those Strings.
DEFINITION
Class: Dance
Method: numDances
Parameters: String[]
Returns: int
Method signature (be sure your method is public): int numDances(String[]
wishes);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- wishes contains between 1 and 10 elements inclusive
- each element of wishes will have between 3 and 50 characters inclusive
- each element of wishes consists of the uppercase letters ('A'-'Z') and spaces
- each element of wishes starts and ends with a letter
- each element of wishes has at least one space, and no two spaces in a row
- each element of wishes will not have repeated names
EXAMPLES
1. wishes = {"ALICE BOB DAVID", "BOB ALICE"} returns 1 as only ALICE and BOB
are willing to dance with each other
2. wishes = {"ALICE BOB DAVID", "BOB DAVID"} returns 0
3. wishes = {"ALICE BOB DAVID", "BOB ALICE CAROL", "CAROL BOB DAVID", "DAVID
ALICE CAROL"} returns 6 as there are 4 ways to arrange a dance with one pair of
dancers and two ways to arrange a dance with two pairs of dancers
4. wishes = {"A B D", "C D", "B A", "D A C"} returns 4 as there are 3 ways to
arrange a dance with one pair: A-B or A-D or C-D and one way to arrange a dance
with two pairs: A-B and C-D.
5. wishes = {"A X", "B Y", "C Z", "B X", "C Y", "X A", "Y B", "Z C", "X B", "Y
C"}, returns 12
6. wishes = {"A B C D E F G H I J", "B A C D E F G H I J", "C A B D E F G H I
J", "D A B C E F G H I J", "E A B C D F G H I J", "F A B C D E G H I J", "G A B
C D E F H I J", "H A B C D E F G I J", "I A B C D E F G H J", "J A B C D E F G
H I"}, returns 9495