Given the standings in a sports division at some point during the season, determine which teams have been mathematically eliminated from winning their division.
The baseball elimination problem. In the baseball elimination problem, there is a division consisting of N teams. At some point during the season, team i has w[i] wins, l[i] losses, r[i] remaining games, and g[i][j] games left to play against team j. (Note that a team's total number of remaining games does not necessarily equal the number of remaining games against divisional rivals since teams may play opponents outside of their own division.) A team is mathematically eliminated if it cannot possibly finish the season in (or tied for) first place. The goal is to determine exactly which teams are mathematically eliminated. The problem is not as easy as many sports writers would have you believe, in part because the answer depends not only on the number of games won and left to play, but also on the schedule of remaining games. To see the complication, consider the following scenario:
w[i] l[i] r[i] g[i][j]
i team wins loss left Atl Phi NY Mon
------------------------------------------------
0 Atlanta 83 71 8 - 1 6 1
1 Philadelphia 80 79 3 1 - 0 2
2 New York 78 78 6 6 0 - 0
3 Montreal 77 82 3 1 2 0 -
Montreal is mathematically eliminated since it can finish with at most 80 wins and Atlanta already has 83 wins. This is the simplest reason for elimination. However, there can be more complicated reasons. For example, Philadelphia is also mathematically eliminated. It can finish the season with as many as 83 wins, which appears to be enough to tie Atlanta. But this would require Atlanta to lose all of its remaining games, including the 6 against New York, in which case New York would finish with 84 wins. We note that New York is not yet mathematically eliminated despite the fact that it has fewer wins than Philadelphia.
It is sometimes not so easy for a sports writer to explain why a particular team is mathematically eliminated. Consider the following scenario from the American League East on August 30, 1996:
w[i] l[i] r[i] g[i][j]
i team wins loss left NY Bal Bos Tor Det
---------------------------------------------------
0 New York 75 59 28 0 3 8 7 3
1 Baltimore 71 63 28 3 0 2 7 4
2 Boston 69 66 27 8 2 0 0 0
3 Toronto 63 72 27 7 7 0 0 0
4 Detroit 49 86 27 3 4 0 0 0
It might appear that Detroit has a remote chance of catching New York and winning the division because Detroit can finish with as many as 76 wins if they go on a 27-game winning steak, which is one more than New York would have if they go on a 28-game losing streak. Try to convince yourself that Detroit is already mathematically eliminated. Here's one explanation; we provide a simpler explanation below.
A maxflow formulation. We now solve the baseball elimination problem by reducing it to the maxflow problem. To check whether team x is eliminated, we create a flow network and solve a maxflow problem in it. In the network, feasible integral flows correspond to outcomes of the remaining schedule. There are vertices corresponding to teams (other than team x) and to remaining divisional games (not involving team x). Intuitively, each unit of flow in the network corresponds to a remaining game. As it flows through the network from s to t, it passes from a game vertex, say between teams i and j, then through one of the team vertices i or j, classifying this game as being won by that team, respectively.
More precisely, our network includes the following edges and capacities. We connect an artificial source vertex s to each game vertex i-j and set its capacity to g[i][j]. If a flow uses all g[i][j] units of capacity on this edge, then we interpret this as playing all of these games, with the wins distributed between the team vertices i and j. We connect each game vertex i-j with the two opposing teams to ensure that one of the two teams earns a win. We do not need to restrict the amount of flow on such edges. Finally, we connect each team vertex to an artificial sink vertex t. We want to know if there is some way of completing all the games so that team x ends up winning at least as many as team i. Since team x can win as many as w[x] + r[x] games, we prevent team i from winning more than that many games in total, by including an edge from team vertex i to the sink vertex with capacity w[x] + r[x] - w[i].
If the maxflow saturates all edges leaving s, then this corresponds to assigning winners to all of the remaining games in such a way that no team wins more games than x. If the max flow does not saturate all edges leaving s, then there is no scenario in which team x can win the division. In the FlowNetwork below Detroit is team x = 4.
What the min cut tells us. By solving a maxflow problem, we can determine whether a given team is mathematically eliminated. We would also like to explain the reason for the team's elimination to a friend in nontechnical terms. Here's such an explanation for Detroit's elimination in the American League East example above. With the best possible luck, Detroit finishes the season with 49 + 27 = 76 wins. Consider the subset of teams R = { New York, Baltimore, Boston, Toronto }. Collectively, they already have 75 + 71 + 69 + 63 = 278 wins; since there are 3 + 8 + 7 + 2 + 7 = 27 remaining games among them, these four teams must win at least an additional 27 games. Thus, on average, the teams in R win at least 305 / 4 = 76.25 games. Regardless of the outcome, one team in R will win at least 77 games, thereby eliminating Detroit.
In fact, when a team is mathematically eliminated there always exists such a convincing certificate of elimination, where R is some subset of the other teams in the division. Moreover, you can always find such a subset R by choosing the team vertices on the source side of a min s-t cut in the baseball elimination network. Note that although we solved a maxflow/mincut problem to find the subset R, once we have it, the argument for a team's elimination does not involve any sophisticated mathematics.
Your assignment. Write a program that reads in a sports league and prints out a list of all of the teams that are mathematically eliminated using the following API:
public BaseballElimination(String filename) // create a baseball elimination network from given filename
public int numberOfTeams() // number of teams
public Iterable<String> teams() // all teams
public int wins(String team) // number of wins for given team
public int losses(String team) // number of losses for given team
public int remaining(String team) // number of remaining games for given team
public int against(String team1, String team2) // number of remaining games between team1 and team2
public boolean isEliminated(String team) // is given team eliminated?
public Iterable<String> certificateOfElimination(String team) // subset R of teams that eliminates given team
public boolean checkSolution(Iterable<String> R, String team)
// return true if subset R does eliminate team
// return false if subset R does not eliminate team
If the team is not eliminated, then your certificateOfElimination() should return an Iterable with zero elements. Your checkSolution() should be efficient and not use the flow network that you create. It should return false when R is an Iterable with zero elements.
For each mathematically eliminated team, print one possible subset that eliminates that team. For example, on the input file teams4.txt, your program should output the following.
% more teams4.txt
4
Atlanta 83 71 8 0 1 6 1
Philadelphia 80 79 3 1 0 0 2
New_York 78 78 6 6 0 0 0
Montreal 77 82 3 1 2 0 0
% java BaseballElimination teams4.txt
Philadelphia is eliminated by the subset R = { Atlanta New_York }.
Montreal is eliminated by the subset R = { Atlanta }.
% more teams5.txt
5
New_York 75 59 28 0 3 8 7 3
Baltimore 71 63 28 3 0 2 7 4
Boston 69 66 27 8 2 0 0 0
Toronto 63 72 27 7 7 0 0 0
Detroit 49 86 27 3 4 0 0 0
% java BaseballElimination teams5.txt
Detroit is eliminated by the subset R = { New_York Baltimore Boston Toronto }.
Use this main as a starting point to test your program:
public static void main(String[] args) {
BaseballElimination division = new BaseballElimination(args[0]);
for (String team : division.teams()) {
if (division.isEliminated(team)) {
StdOut.print(team + " is eliminated by the subset R = { ");
for (String t : division.certificateOfElimination(team))
StdOut.print(t + " ");
StdOut.println("}.");
StdOut.println("");
}
}
}
Simplifying assumptions. Assume that no games end in a tie (as is the case in Major League Baseball). Also assume that there are no rainouts, i.e., every scheduled game is played. Ignore wildcard possibilities, where a team can make the playoffs without finishing first in its division. Finally, assume that there are no whitespace characters in the name of a team.
Deliverables. Submit BaseballElimination.java and any other files needed to compile your program (except for files in stdlib.jar and algs4.jar which we will supply). Create and submit your own test input file and call it teams.txt. Your input format must be a correct input format. Finally, submit a readme.txt file. On this assignment, your main goal is to determine the correct answer and interpret your solution. Do not worry about overoptimizing your program because the data sets that come from real applications are quite small.