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

1 | Benq | 3783 |

2 | jiangly | 3772 |

3 | tourist | 3706 |

4 | maroonrk | 3609 |

5 | Um_nik | 3591 |

6 | fantasy | 3526 |

7 | ko_osaga | 3500 |

8 | inaFSTream | 3477 |

9 | cnnfls_csy | 3427 |

10 | zh0ukangyang | 3423 |

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

1 | Um_nik | 183 |

2 | awoo | 181 |

3 | nor | 172 |

4 | -is-this-fft- | 170 |

4 | adamant | 170 |

6 | maroonrk | 165 |

7 | antontrygubO_o | 160 |

8 | SecondThread | 159 |

9 | dario2994 | 152 |

9 | kostka | 152 |

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/23/2023 07:08:55 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Consider a graph with

2 * nvertexes, vertex numbericorresponds to situation when there areipeople that have already been to finals. We have an arc (i,j) in this graph when we can sendkofiexperienced people in team and after it we havejexperienced 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.