Блог пользователя dragoon

Автор dragoon, 13 лет назад, По-английски
http://www.codeforces.com/contest/97/problem/C

Can anyone help with the solution?
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +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.