Suppose n=2^k, a(0), a(1), ..., a(n-1) are the n teams
1. If there are 1 team, then no matches, 0 days needed;
If there are 2 teams, arrange 1 match for them, 1day needed.
2. Split the n teams into 2 groups of equal size, ie.
a(0),a(1),...,a(n/2-1) and a(n/2),a(n/2+1),...,a(n-1).
3. Construct the timetable for each group. Merge the 2 timetables to
form the timetable of first (n/2-1) days.
4. Arrange inter-group matches for the next n/2 days. One of the choices is:
for the next i'th day, let team a(k) plays with a(n/2+(k+i)%(n/2)),
k=0,1,...,n/2-1
The final timetable covers exactly (n-1) days.
On 2010-4-7 14:50, 难躂 换 wrote:
Can any one help me with this problem....
Its a divide and conquer problem where, there are n teams and each
team plays each opponent only once. And each team plays exactly once
every day. If n is the power of 2, I need to construct a timetable
allowing the tournament to finish in n-1 days...
Any help would be appreciated.. thanks
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
