The Crossover - a work in progress

Dormant threads from the high school sections are preserved here.
Locked
User avatar
jonpin
Auron
Posts: 2266
Joined: Wed Feb 04, 2004 6:45 pm
Location: BCA NJ / WUSTL MO / Hackensack NJ

The Crossover - a work in progress

Post by jonpin »

The early posts in this thread are/will be an introduction to this style of tournament format, but later posts will hopefully be of benefit to even experienced TDs.

One of the most common tournament formats for regular season events is prelim groups followed by playoff groups. In some cases, it's most efficient to reset the standings at the mid-tournament rebracketing, but in other cases, it makes sense to carryover and crossover. That is, two (or more) teams are advancing to the same playoff bracket from the same prelim group. Rather than replay the game(s) between those teams in the afternoon, you carry over the result from the morning, and only play those games that are new. This post is meant to demonstrate some of the schedules which are possible, and how best to organize a crossover stage.

Terminology: Letters will indicate prelim groups, numbers will represent teams within those groups, in the order they finished the morning rounds. "Morning" indicates the preliminary stage, "Afternoon" the playoff stage, as in my region the split between the two stages is almost always lunchtime.

Example: Starting with 16 teams in 2 groups of 8, you might play a round-robin, and then split into top 4 and bottom 4 for crossover rounds. Then the teams in the top bracket are A1, A2, A3, A4; B1, B2, B3, B4. Each team enters the afternoon with 3 games already counting from the morning (note that A1 does not necessarily carry over 3 wins). Then a possible afternoon schedule is:

Code: Select all

Rd Rm #1 Rm #2 Rm #3 Rm #4
#1 A1-B4 A2-B3 A3-B2 A4-B1
#2 A4-B2 A3-B1 A2-B4 A1-B3 
#3 A2-B1 A1-B2 A4-B3 A3-B4
#4 A3-B3 A4-B4 A1-B1 A2-B2
In addition to the requirement that each A team plays each B team, this has the aesthetic benefits of getting the mismatches out of the way early and building up to A1 v B1 in the last round (if they both stay undefeated and you're using the advantage final system, the last round serves as the first game of a 3-game final). Also, each team plays in each room once. Sometimes that last bit is not possible, but it is certainly preferable to one or more teams staying in the same room for several rounds in a row.

Where this gets difficult is when there are more than two prelim groups feeding into a crossover. I was inspired to create this thread while planning the format for ACF Nationals. Some potential formats involved a 15-team crossover, with 5 teams each coming from 3 groups. With each team having to play 10 games, can this be accomplished in 10 rounds? No, since with an odd number of teams, not everyone plays each round? Can it be done in 11? Yes. Is there an elegant way to create such a schedule? Maybe, but I brute forced it. It's the same kind of situation that occurred in the top tier of the 2013 NSC, where the top bracket had nine teams, the top three from each of three semifinal groups. Seven rounds, rather than six, were required because of the necessary byes. What about a case where the bottom bracket has three teams from group A, but two from groups B and C?

So the point of this thread, which I hope to build over the next week or two, is to compile crossover formats for differing numbers of teams, as a service to the QB community. If you have any feedback or schedules to contribute, feel free to chime in.
Jon Pinyan
Coach, Bergen County Academies (NJ); former player for BCA (2000-03) and WUSTL (2003-07)
HSQB forum mod, PACE member
Stat director for: NSC '13-'15, '17; ACF '14, '17, '19; NHBB '13-'15; NASAT '11

"A [...] wizard who controls the weather" - Jerry Vinokurov
User avatar
Cody
2008-09 Male Athlete of the Year
Posts: 2891
Joined: Sun Nov 15, 2009 12:57 am

Re: The Crossover - a work in progress

Post by Cody »

From what I remember:

Constructing a crossover is finding the perfect matchings for an n-partite graph (near-perfect, when n is odd) with # of vertices = # of teams. (equivalently,* finding the 1-factors of a 1-factorization). Though I haven't tried, this can be done in Sage (cf. http://linear.ups.edu/eagts/section-19.html).

Ophir once gave a nice visualization of this for 3 brackets, so he may be aware of how to do it programmatically.

*perhaps not equivalently when n is odd
Cody Voight, VCU ’14.
User avatar
jonpin
Auron
Posts: 2266
Joined: Wed Feb 04, 2004 6:45 pm
Location: BCA NJ / WUSTL MO / Hackensack NJ

Re: The Crossover - a work in progress

Post by jonpin »

Well why you gotta turn everything into a math problem? :smile:

Crossing over from two groups
This is one of the two easiest forms to set up. If the two groups are each contributing the same number of teams (A1, A2... An; B1, B2... Bn), it will take n rounds in n rooms. As noted above, it looks nicest if A1 v B1 is the last round, but it won't always be possible to build a symmetric (i.e. A1-B3 is at the same time as A3-B1) schedule that ends with A1-B1, A2-B2, A3-B3, etc. Some examples of schedules:

Code: Select all

3-3, symmetric
Rd Rm #1 Rm #2 Rm #3
#1 A1-B3 A2-B2 A3-B1
#2 A2-B1 A3-B3 A1-B2
#3 A3-B2 A1-B1 A2-B3

Code: Select all

3-3, ends with like playing like
Rd Rm #1 Rm #2 Rm #3
#1 A3-B2 A1-B3 A2-B1
#2 A2-B3 A3-B1 A1-B2
#3 A1-B1 A2-B2 A3-B3
A 4-4 schedule that is both symmetric and ends with like-playing-like is in the original post.

Only slightly trickier is if your two groups are contributing an unequal number of teams. This is most common for the bottom playoff bracket, as you might, for instance, start with a group of 8 and a group of 7, and take the top three from each to the first bracket, next three from each to the second bracket, and everyone else to the bottom bracket. All you really need to do to make this kind of schedule is eliminate the highest numbered B-team and compress vertically. For instance, to make the 4-3 schedule:

Code: Select all

Starting with a 4-4, remove the games involving B4
Rd Rm #1 Rm #2 Rm #3 Rm #4
#1 ..... A2-B3 A3-B2 A4-B1
#2 A4-B2 A3-B1 ..... A1-B3
#3 A2-B1 A1-B2 A4-B3 .....
#4 A3-B3 ..... A1-B1 A2-B2

Then compress
Rd Rm #1 Rm #2 Rm #3 Bye
#1 A2-B3 A3-B2 A4-B1 A1
#2 A4-B2 A3-B1 A1-B3 A2
#3 A2-B1 A1-B2 A4-B3 A3
#4 A3-B3 A1-B1 A2-B2 A4
Note that a 4-3 takes 4 rounds, but only 3 rooms. A 3-2 takes 3 rounds in 2 rooms, and so forth.
Jon Pinyan
Coach, Bergen County Academies (NJ); former player for BCA (2000-03) and WUSTL (2003-07)
HSQB forum mod, PACE member
Stat director for: NSC '13-'15, '17; ACF '14, '17, '19; NHBB '13-'15; NASAT '11

"A [...] wizard who controls the weather" - Jerry Vinokurov
User avatar
Whiter Hydra
Auron
Posts: 1418
Joined: Tue Dec 04, 2007 8:46 pm
Location: Fairfax, VA
Contact:

Re: The Crossover - a work in progress

Post by Whiter Hydra »

If you're only taking the top two teams from each bracket into the playoffs, it's fairly easy to make a crossover-format schedule. Simply make a standard round-robin schedule, assign the teams such that the two teams from each bracket will play each other round 1, and then skip that round.

For example, if you have four brackets each bringing two teams, make an eight-team round-robin schedule.

Code: Select all

3-5  6-7  2-4  1-8
1-3  2-8  4-6  5-7
3-7  4-5  6-8  1-2
(And so on...)
Replace the numbers with bracket designations (3 -> A1, 5 -> A2, etc.).

Code: Select all

A1-A2  B1-B2  C1-C2  D1-D2
D1-A1  C1-D2  C2-B1  A2-B2
A1-B2  C2-A2  B1-D2  D1-C1
(And so on...)
And get rid of the first round.

Code: Select all

D1-A1  C1-D2  C2-B1  A2-B2
A1-B2  C2-A2  B1-D2  D1-C1
(And so on...)
Harry White
TJHSST '09, Virginia Tech '13

Owner of Tournament Database Search and Quizbowl Schedule Generator
Will run stats for food
User avatar
Mewto55555
Tidus
Posts: 709
Joined: Sat Mar 13, 2010 9:27 pm

Re: The Crossover - a work in progress

Post by Mewto55555 »

Cody wrote:From what I remember:

Constructing a crossover is finding the perfect matchings for an n-partite graph (near-perfect, when n is odd) with # of vertices = # of teams. (equivalently,* finding the 1-factors of a 1-factorization). Though I haven't tried, this can be done in Sage (cf. http://linear.ups.edu/eagts/section-19.html).

Ophir once gave a nice visualization of this for 3 brackets, so he may be aware of how to do it programmatically.

*perhaps not equivalently when n is odd
Fact (useless for practical scheduling but this is the "theory" forum after all! :razz:): if you just schedule a 2-bracket crossover round-by-round, then you'll always be able to find a working schedule for each round, without having to alter a previous round's schedule to make it work, because all regular bipartite graphs with equal size parts have a perfect matching!
Max
formerly of Ladue, Chicago
User avatar
Cody
2008-09 Male Athlete of the Year
Posts: 2891
Joined: Sun Nov 15, 2009 12:57 am

Re: The Crossover - a work in progress

Post by Cody »

I'm pretty sure that is true of most crossovers involving an even number of teams (even # of brackets or even # of teams), at least in my experience. It's not so easy w/ odd # of teams though.
Cody Voight, VCU ’14.
User avatar
Cody
2008-09 Male Athlete of the Year
Posts: 2891
Joined: Sun Nov 15, 2009 12:57 am

Re: The Crossover - a work in progress

Post by Cody »

Generating many-bracket crossovers by hand can be a bit tricky, but it becomes dramatically simpler if you remember one simple thing: a crossover is just a round robin where some of the games have already been played (which is commonly understood, but often not stated explicitly). For example, trying to generate a crossover of 3 teams from 4 brackets can be a daunting task until you reconceptualize it as a 12-team round robin. The tables transfer only decently to the forums, so you can refer to this spreadsheet as well.

Keep in mind that smaller crossovers are generally easy to generate by hand or with Harry White's method above, so this post mostly applies to large crossovers of the type that you see at national tournaments.

Code: Select all

Round	Room 1	Room 2	Room 3	Room 4	Room 5	Room 6
1	2 v 11	1 v 12	3 v 10	4 v 9	5 v 8	6 v 7
2	5 v 9	6 v 8	1 v 7	4 v 10	3 v 11	2 v 12
3	5 v 10	3 v 12	4 v 11	1 v 2	6 v 9	7 v 8
4	4 v 12	7 v 9	6 v 10	5 v 11	1 v 8	2 v 3
5	8 v 9	2 v 4	5 v 12	6 v 11	7 v 10	1 v 3
6	3 v 4	8 v 10	7 v 11	6 v 12	2 v 5	1 v 9
7	8 v 11	3 v 5	2 v 6	7 v 12	1 v 4	9 v 10
8	2 v 7	9 v 11	8 v 12	1 v 10	3 v 6	4 v 5
9	3 v 7	4 v 6	1 v 5	2 v 8	9 v 12	10 v 11
10	10 v 12	1 v 11	2 v 9	3 v 8	4 v 7	5 v 6
11	1 v 6	5 v 7	4 v 8	3 v 9	2 v 10	11 v 12
Let's call our brackets A, B, C, D and number our finishers by W–L. Replace 1–3 with A1–A3, 4–6 with B1–B3, 7–9 with C1–C3, and 10–12 with D1–D3.

Code: Select all

Round	Room 1	Room 2	Room 3	Room 4	Room 5	Room 6
1	A2 v D2	A1 v D3	A3 v D1	B1 v C3	B2 v C2	B3 v C1
2	B2 v C3	B3 v C2	A1 v C1	B1 v D1	A3 v D2	A2 v D3
3	B2 v D1	A3 v D3	B1 v D2	A1 v A2	B3 v C3	C1 v C2
4	B1 v D3	C1 v C3	B3 v D1	B2 v D2	A1 v C2	A2 v A3
5	C2 v C3	A2 v B1	B2 v D3	B3 v D2	C1 v D1	A1 v A3
6	A3 v B1	C2 v D1	C1 v D2	B3 v D3	A2 v B2	A1 v C3
7	C2 v D2	A3 v B2	A2 v B3	C1 v D3	A1 v B1	C3 v D1
8	A2 v C1	C3 v D2	C2 v D3	A1 v D1	A3 v B3	B1 v B2
9	A3 v C1	B1 v B3	A1 v B2	A2 v C2	C3 v D3	D1 v D2
10	D1 v D3	A1 v D2	A2 v C3	A3 v C2	B1 v C1	B2 v B3
11	A1 v B3	B2 v C1	B1 v C2	A3 v C3	A2 v D1	D2 v D3
Pull out the games that have already been played (any games between the same prelim bracket) and list them as byes.

Code: Select all

Round	Room 1	Room 2	Room 3	Room 4	Room 5	Room 6	BYE
1	A2 v D2	A1 v D3	A3 v D1	B1 v C3	B2 v C2	B3 v C1	
2	B2 v C3	B3 v C2	A1 v C1	B1 v D1	A3 v D2	A2 v D3	
3	B2 v D1	A3 v D3	B1 v D2		B3 v C3		A1,A2,C1,C2
4	B1 v D3		B3 v D1	B2 v D2	A1 v C2		A2,A3,C1,C3
5		A2 v B1	B2 v D3	B3 v D2	C1 v D1		A1,A3,C2,C3
6	A3 v B1	C2 v D1	C1 v D2	B3 v D3	A2 v B2	A1 v C3	
7	C2 v D2	A3 v B2	A2 v B3	C1 v D3	A1 v B1	C3 v D1	
8	A2 v C1	C3 v D2	C2 v D3	A1 v D1	A3 v B3		B1,B2
9	A3 v C1		A1 v B2	A2 v C2	C3 v D3		B1,B3,D1,D2
10		A1 v D2	A2 v C3	A3 v C2	B1 v C1		B2,B3,D1,D3
11	A1 v B3	B2 v C1	B1 v C2	A3 v C3	A2 v D1		D2,D3
The minimum number of rounds for a crossover is the number of new games played by a team (+1 if there are an odd number of teams). Each team plays 11 games in a 12-team round robin, and has already played 2 games, yielding 9 new games. (Alternatively, count the number of teams going to a playoff bracket from each prelim bracket and multiply by the number of prelim brackets minus one.) Rearranging the games just a little bit condenses into 9 rounds. (Alternatively, if you are room-constrained instead of round-constrained, you can rearrange the 54 games into 5 rooms across 11 rounds).

Code: Select all

Round	Room 1	Room 2	Room 3	Room 4	Room 5	Room 6	BYE
1	A2 v D2	A1 v D3	A3 v D1	B1 v C3	B2 v C2	B3 v C1	
2	B2 v C3	B3 v C2	A1 v C1	B1 v D1	A3 v D2	A2 v D3	
3	B2 v D1	A3 v D3	A1 v D2	A2 v C2	B3 v C3	B1 v C1	
4	B1 v D3	A3 v C3	B3 v D1	B2 v D2	A1 v C2	A2 v C1	
5	A3 v C2	A2 v C3	B2 v D3	B1 v D2	C1 v D1	A1 v B3	
6	A3 v B1	C2 v D1	C1 v D2	B3 v D3	A2 v B2	A1 v C3	
7	C2 v D2	A3 v B2	A2 v B3	C1 v D3	A1 v B1	C3 v D1	
8	B2 v C1	C3 v D2	C2 v D3	A1 v D1	A3 v B3	A2 v B1	
9	A3 v C1	A2 v D1	A1 v B2	B3 v D2	C3 v D3	B1 v C2	
10							
11							
There are two keys to reordering the games: (1) set up an error-checking routine that counts the number of teams before moving any games (e.g. COUNTIF(range, "*A1*") for A1 through D3) and (2) move games from late rounds to fill out the byes in the earlier rounds, then switch around games as needed. Some games from rounds 1–9 will need to be moved around to make the schedule work. The spreadsheet indicates which games were moved from rounds 10–11 and which had to be moved from rounds 1–9. A schedule with the optimal number of rounds is guaranteed to exist, so if at first you don't succeed you can keep going or restart. While reordering takes some work, I have found it takes far less time than writing it out by hand.

This methodology works especially well for odd-team crossovers (i.e. an odd number of teams from an odd number of brackets, usually a 3-bracket, 3-team crossover) or crossovers involving more than 3+ uneven brackets, since they can be much harder to generate by hand.
Cody Voight, VCU ’14.
Locked