Internet Problem Solving Contest

IPSC 2002

Solution to Problem F – (un)Fair Play

Clearly if there is a solution, there is a solution where team N wins all its remaining matches. Let N have P points after winning all its remaining matches. If some other team has at least P points, there is no solution. Otherwise, we have to distribute the points from the remaining matches between the other teams in such a way that no team reaches or exceeds P points. We transform this task to an integer network flow problem.

Consider a graph with 2+M+(N-1) vertices – a source, a sink, one vertex for each remaining match and one for each team except the team N. From the source, an edge with capacity 2 leads into each match-vertex (*). From each match-vertex two edges with unlimited capacity lead into team-vertices of the two teams playing the match (**). From each team-vertex an edge leads to the sink (***). The capacity of this edge will be the maximum number of points the team may still gain.

Edges (*) give each match two points to distribute. Edges (**) allow these points to be distributed between the corresponding teams. Edges (***) enforce that after distributing the points, each team will have less points than team N.

To solve the task, it suffices to find the maximum flow in the constructed graph (e.g. using the Ford-Fulkerson algorithm) and verify, whether its value is 2M – in other words, whether it is possible to distribute all the remaining points.