TopCoder problem "TournamentSchedule" used in TCHS SRM 14 (Division I Level Three)



Problem Statement

    

You are organizing a basketball tournament for teams from your neighborhood. An even number of teams, numTeams, has registered. You want the tournament to last numTeams - 1 rounds, where numTeams/2 matches are played simultaneously in each round. Each team must play each of the other teams exactly once during the tournament. You predict that some of the matches will be particularly exciting, so you want to schedule them during specific rounds.

You are given a String[] preferences, where each element is formatted:

<Round>:<TeamA>-<TeamB>
where <Round> is the zero-based number of the round, and <TeamA> and <TeamB> are zero-based team numbers. Return the number of different tournament schedules that will satisfy all the preferences. Return 0 if no schedule can satisfy all the preferences.

Two schedules A and B are different if there exists a round in which a team plays a different opponent in A than it does in B. For example, if the same round in two schedules are as follows: 

schedule A        schedule B
   0-1               3-2
   2-3               0-1

they are the same, but

schedule A        schedule B
   0-1               0-2
   2-3               1-3

are different.
 

Definition

    
Class:TournamentSchedule
Method:ways
Parameters:int, String[]
Returns:int
Method signature:int ways(int numTeams, String[] preferences)
(be sure your method is public)
    
 

Constraints

-numTeams is an even number between 2 and 6, inclusive.
-Each element of preferences is formatted as "<Round>:<TeamA>-<TeamB>" (quotes for clarity only).
-Each <Round> is an integer between 0 and numTeams - 2, inclusive, with no extra leading zeroes.
-Each <TeamA> and <TeamB> is an integer between 0 and numTeams - 1, inclusive, with no extra leading zeroes.
-In each element of preferences, <TeamA> is different from <TeamB>.
-preferences will contain between 1 and 50 elements, inclusive.
 

Examples

0)
    
4
{"0:0-1"}
Returns: 2
In the first round we want the first two teams to play together. The other match of that round must be between teams 2 and 3. Now we have two choices to set up round 1 : 
1:2   or   1:3
0:3        0:2
After deciding on round 1 there would be only one valid set up of round 2.
1)
    
4
{"0:0-1","1:1-2"}
Returns: 1
Here we don't have the flexibility of setting up round 1 that we had in the previous example. There is only one possible schedule.
2)
    
4
{"0:0-1","0:0-1","1:1-2","0:2-3","1:3-0"}
Returns: 1
This is similar to example 1. We added two more restrictions, but they don't change anything because these are the matches we would have chosen anyway. Note that there can be duplicate entries in preferences.
3)
    
4
{"0:1-0","0:1-2"}
Returns: 0
The preferences cannot be satisfied because team 1 can only play one match in round 0.
4)
    
6
{"0:3-4", "3:2-1", "4:1-4"}
Returns: 8

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6722

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10066&pm=6722

Writer:

slex

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Brute Force