Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

froggy's blog

Single Round Robin Tournament algorithm
By froggy, 13 years ago, In English

I encountered this problem today, haven't come up with the optimal solution yet :(

So the problem is given you N teams (N is even), find a way to arrange the matches so that the differences between the number of home matches and away matches of each team is at most 1.

Is it possible to find such an arrangement? Please help :( Thank you very much!

UPD: Each team shouldn't play more than 2 Home matches or 2 Away matches in a row. Can this problem be possible to solve with this constraint as well?

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

the statement of this problem is very ambiguous!

→ Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Sorry about my bad English :( But I don't know how to make it clearer :(

    → Reply
    • »
      »
      »
      13 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      just explain it in more details , what do you mean with "home" match and "away" match isn't the same match is "home" for one of the two teams playing against each other and "away" for the other team?

      you can also give an example to make the problem clearer

      → Reply
      • »
        »
        »
        »
        13 years ago, hide # ^ |
        ← Rev. 5  
        Vote: I like it 0 Vote: I do not like it

        Another forumulation could be:

        There are N teams and N stadiums; the i-th stadium is a home stadium of the i-th team. There are matches; every match is held between two different teams {a, b} at one of the stadiums a, b. We'll call a match for team i, which played in that match, a home match iff it's held at stadium i; otherwise, we'll call it (for team i) an away match. We'll call an assignment of matches to stadiums good if the absolute difference between the number of home matches and away matches for each team is  ≤ 1. Given N, find out whether any good asignment exists.

        UPD: We'll call an assignment of matches (in some order) to stadiums good if the absolute difference between the number of home matches and away matches for each team is  ≤ 1 and the sequence of matches in which team i played doesn't contain three successive home or away matches for team i. Given N, find out whether any good asignment exists.

        Good enough? :D

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          regarding ur UPD, the sequence of matches can contain two successive home or away matches for any team, but not more than two.
          so 1-2 1-3 4-1 is a valid sequence (as far as team 1 is concerned).

          also, if two successive home or away matches are also not allowed, then the answer is always zero (except N=2). this is because u will have to split the teams into two parts (kind of like a bipartite graph), which would mean the teams in the same "part" would never play against each other.

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Oh. Yeah, that. And if two successive home/away matches weren't allowed, then the sequence of matches for every team would have to be alternating ...-home-away-home-away-...

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              13 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              yes. every team plays either HAHAHA... or AHAHAH... due to two successive not allowed. so half the teams play home on even matches and away on odd matches, and the other half vice-versa.
              this would mean that teams in the same "half" will never play against each other!

              → Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hint: divide teams into pairs

→ Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Suppose that one need to arrange 1 match between every 2 teams (n·(n - 1) / 2 matches in total). Then each team plays home with teams who have even numbers and away with teams who have odd numbers.

→ Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thanks for your comment! Sorry but I don't quite get your idea yet :(

    → Reply
    • »
      »
      »
      13 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      It's not actual anymore with your update.

      But let's discuss the algorithm described here that you mentioned already.

      There's n / 2 columns. Let's enumerate them. Except column #1, teams change other n - 1 columns on every step + sometimes they happen to be in one cell of column #1. So let's do such plan:

      1 2 3 4

      8 7 6 5

      H A H A

      A H A H

      So every time when team changes its place, "home" or "away" label changes as well. Probably there can be corner case in column #1 when you don't change "away" but it doesn't prohibited in your statement to have 2 matches in a row either home or away.

      Moreover, you need to take into account team #1 separately — for example, in rounds with even number that team plays home, in rounds with odd number that team plays away.

      → Reply
»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Really great Discrete optimization course on Coursera had a lecture on similar topic. Maybe there task was a bit different, I don't remember for sure, but might be useful to listen to anyway.

→ Reply
»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

This is how it's solved in chess tournaments:

Digits in the table are numbers of rounds:

*2345671
2*456713
34*67125
456*1237
5671*342
67123*54
712345*6
1357246*

And the colors (white or black):

*WBWBWBW
B*WBWBWW
WB*WBWBW
BWB*WBWW
WBWB*WBB
BWBWB*WB
WBWBWB*B
BBBBWWW*

(Last player has always BBB..BBBWWW..WWW, in other games if playerID1 < playerID2 and they have the same parity, player with bigger ID plays white.

→ Reply
  • »
    »
    13 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    So it's kind of a real life problem :D

    Except this allows more than 2 successive matches with the same colour, violating condition UPD.

    → Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    can u explain how u got this "chessboard"?
    i'm not sure, but i guess it will work for N > 8 also. is that right?

    → Reply