HomeAwayLeague
TCO19 SRM 760 · 2019-06-11 · by teja349
Problem Statement
There are N football teams in the region. The number N is even. Each team has it own home stadium.
The league committee has decided to organize a short summer league for all N teams. The league should have the following properties:
- The league will consist of exactly two rounds of football matches.
- Each team will play one match in each round.
- Each pair of teams will play each other at most once.
- It is well known that playing at its home stadium gives the team a slight advantage. To keep the league fair, each team must play exactly one home game and one away game.
Count all valid league schedules and return that count modulo 10^9 + 7.
Formally: A match is an ordered pair (home team, away team). A round schedule is an unordered set of matches such that each team appears in exactly one match. A league schedule is an ordered pair of round schedules.
Constraints
- N will be between 4 and 500,000, inclusive.
- N will be even.
4 Returns: 12
Let's use (X,Y) to denote a match where X is the home team and Y is the away team, i.e., a match played at X's home stadium. Here are three of the twelve distinct valid league schedules: First round: (A,B), (C,D). Second round: (B,C), (D,A). First round: (A,B), (D,C). Second round: (B,D), (C,A). First round: (C,A), (B,D). Second round: (A,B), (D,C). Note that the third schedule can be obtained from the second one by swapping the order of the rounds. These two schedules are considered distinct.
6 Returns: 240
8 Returns: 15120
10 Returns: 1330560
12 Returns: 176299200
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HomeAwayLeague with a public method int matches(int x) · 56 test cases · 2 s / 256 MB per case