dragoon's blog

Yandex Final - Problem C
By dragoon, 13 years ago, In English
http://www.codeforces.com/contest/97/problem/C

Can anyone help with the solution?
  • Vote: I like it
  • +1
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
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.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks :) Nice problem, simple soln but not obvious :)
    → Reply