You are organizing a 1 v 1 basketball league with a game calendar. At the end of the league, he has each player report his supposed record of wins and losses (there are no draws), but he wants to verify if the proposed rankings were really possible given the calendar.
For example: you have four players (Alice + Bob + Carol + Dave) and your agenda is a simple round robin. The reported classification (A: 3-0 SECOND: 1-2 DO: 1-2 RE: 1-2) and (A: 2-1 SECOND: 1-2 DO: 1-2 RE: 2-1) would be possible, but the position (A: 3-0 SECOND: 0-3 DO: 0-3 RE: 3-0) it wouldn't be.
Now suppose the schedule is a 3-game face-to-face game between Alice + Bob and Carol + Dave. The reported position (A: 3-0 SECOND: 0-3 DO: 0-3 RE: 3-0) is now possible, but (A: 3-0 SECOND: 1-2 DO: 1-2 RE: 1-2) it would not be anymore.
(The schedule does not need to be symmetrical in any way. It could make Alice only play against Bob 10 times, then have Bob + Carol + Dave play 58 round robins against each other.)
issue: Given a schedule with k participants and north Total games, efficiently check if the proposed win-lose ranking could actually occur from that calendar.
The O ($ 2 ^ n $) The brute force method is obvious, list all possible game results and see if any match the proposed classification. What if k is small increasing north It does not add much complexity: it is very easy to verify the classification of a league of two people regardless of whether they play ten or ten billion games. Beyond that, I have not advanced much in the search for a better method, and I was curious to know if anyone had seen a similar problem before.