How can I solve the problem Hooligan?, problem H of the ACM-ICPC Latin American Contest 2009. Could anyone help me? http://coj.uci.cu/24h/problem.xhtml?pid=1210

Before contest

Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

12:25:01

Register now »

Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)

12:25:01

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | Um_nik | 3309 |

3 | Petr | 3298 |

4 | dotorya | 3225 |

5 | W4yneb0t | 3218 |

6 | OO0OOO00O0OOO0O0…O | 3199 |

7 | Radewoosh | 3150 |

8 | izrak | 3109 |

9 | anta | 3106 |

10 | Syloviaely | 3073 |

# | User | Contrib. |
---|---|---|

1 | tourist | 186 |

2 | rng_58 | 175 |

3 | csacademy | 167 |

4 | Petr | 160 |

5 | Swistakk | 156 |

6 | Errichto | 150 |

7 | lewin | 149 |

8 | Zlobober | 144 |

9 | matthew99 | 141 |

9 | adamant | 141 |

How can I solve the problem Hooligan?, problem H of the ACM-ICPC Latin American Contest 2009. Could anyone help me? http://coj.uci.cu/24h/problem.xhtml?pid=1210

↑

↓

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/20/2018 06:09:59 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

First, we suppose greedily that our dream team wins all of its missing matches. After this, it should have

Ppoints. Then, build a graph with nodesx_{1},x_{2}, ...,x_{n - 1}. Now, betweenx_{i}andx_{j}(i≠j), put an edge in each direction with capacity equal to the number of games missing between teamsiandj. Use a nodeB, which has an edge towards everyx_{i}with capacity equal to the number of matches thei^{th}team still has to play, and a nodeE, in such a way that there is an edge from eachx_{i}to this node with capacity equal toP-p_{i}, wherep_{i}are the points that thei^{th}team already has. Your dream team can be a champion iff the maxflow fromBtoEequals the number of missing matches.Do you consider whether the team wins, loses or draw?

Yes. I am considering that each team wins 1 point per every game that it has not played (This happens because every match distributes 2 points, so 1 per team). This amount of points is the flow from

Btox_{i}. After that, each team can "transfer" one point to other team, with the constraint that it cannot transfer more points than the matches that they can play between them. A point transfer fromx_{i}tox_{j}means that teamilose to teamj. If no transfer occurs, theniandjdrew their game.Thanks. Could you send me your code?

Sorry, I haven't coded it yet :/

This is a famous Max Flow problem, more info here