### dragoon's blog

By dragoon, 11 years ago,
http://www.codeforces.com/contest/97/problem/C

Can anyone help with the solution?

• +1

 11 years ago, # |   +6 I can offer you author's solution, cause it's my problem :)Consider a graph with 2 * n vertexes, vertex number i corresponds to situation when there are i people that have already been to finals. We have an arc (i, j) in this graph when we can send k of i experienced people in team and after it we have j experienced people (i.e. j = n + i - 2 * k, 0<=k <= i). It's obvious that each infinite path in this graph corresponds to some coach's strategy. One can prove, that one of optimal strategies is repetition of simple cycle in such a graph. That means you should find a cycle with lowest average weight in this graph. You can do it using combination of binary search and Bellman-Ford algorithm for finding cycles of negative weight.By the way contestants found an O(n^2) solution, by unfortunately nobody have explained me why does it work yet. It would be great if somebody tells us it.
•  11 years ago, # ^ |   0 Thanks :) Nice problem, simple soln but not obvious :)