Re: [algogeeks] Divide and Conquer problem
Following are the recurrences: T(n)=2T(n/2)+1 T(2)=1 T(n)=n-1 =O(n) 1 is added because winner of both the sides will compete at most 1 once. for Time table u can form a tree x1 x2 x3 x4 x5 \ / \ / / x1 x3 / \ \ / \ x5 \ / x1 Here are four matches and team nos =5 On Wed, Apr 7, 2010 at 12:20 PM, «« ÄÑÜJ »» anujlove...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Divide and Conquer problem
You 've got n teams and nC2 ways of conducting the matches with specified constraints that's n/2(n-1). So, each day you need to conduct n/2 matches such that, no team repeats within a day, no match that was previously held repeats. Since the problem has an unique solution, you can either brute force it with a program or design an back track solution. regards, vignesh On 7 April 2010 12:20, «« ÄÑÜJ »» anujlove...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Divide and Conquer problem
@ ashish .. each team should play the other team at least once. in merging that thing does not happen. On Thu, Apr 8, 2010 at 9:42 AM, Ashish Mishra amishra@gmail.com wrote: Can it be done in more or less like merge sort way i.e 1. divide array into half 2. keep on doing it till u have two element left 3. arrang match between two and return winner On Wed, Apr 7, 2010 at 12:20 PM, «« ÄÑÜJ »» anujlove...@gmail.com 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- How soon 'not now' becomes 'never'... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Divide and Conquer problem
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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Divide and Conquer problem
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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
