Wpadam na proste rozwiązanie: zakładam, że mam łącznie N zawodników, następnie zachlanie wsadzam ich w domki. Liczba meczy w domku a_i to wielomian od mieszkańców po lewej (już obsadzonych), mieszkańców, ktorych przypiszę do a_i, oraz tych mieszkających po prawej (nierozlokowanych jeszcze mieszkańców). Uda się lub nie. Binarnie szukamy najmniejszego N.

Wygląda dobrze, ale pewnym nigdy być nie można (no, chyba, że dowodzik...). Zeby sprawdzić na szybko, zamiast rozwiązywać ten wielomian (aż 3 stopnia względem mieszkanców w i-tym domku) podrzędnie iteruję od 0 aż liczba meczy dogoni oczekiwaną (albo skończą się mieszkańcy). Badziewne rozwiązanie, ale też mieszkańców najczęściej będzie mało. Testy przechodzi, sprawdzarkę... sprawdzarka ma długa kolejkę. No to robimy porządnie.

Ten wielomian jest niemalejący na odcinku 0...nierozdzieleni mieszkańcy (może nie widać tego po wielomianie, ale widać po interpretacji, przeniesienie kogoś z prawej strony do i-tego domku nie zmiejsza liczby meczy w i-tym). No to kolejne wyszukiwanie binarne.

I... co prawda działa*), ale wolniej niż "brut".

*) działa po poprawkach, posłałem wersję ze zbyt optymistycznym szacowaniem górnej granicy poszukiwań, przez co przekręcam licznik int64_t ;-) Na szczęście w miedzyczasie sprawdzarka oceniła bruta na 10, to nie czekajac na wyniki "poprawionej" wersji posłałem bruta raz jeszcze.

BTW. W przypadku C, gdzie wyniki są odsłaniane, pewnie można by rozważyć branie najlepszego wyniku, nie najnowszego. Zawodnik it tak może posłać 9 wersji i wybrać najlepszą.

Iterując się od 0 do znalezienia minimalnej wartości, dla której działa wykonasz łącznie N iteracji. Gdy na którejś pozycji zrobisz x iteracji to na dalszych pozycjach zostanie Ci N-x. Zamortyzowany czas na pojedynczą pozycje to O(N/n). Złożoność tego rozwiązania to O(NlogN) < O(Nlog^2N), dla "lepszego" rozwiązania.

Cały czas umyka mi jeden szczegół... w jaki sposób sprawdzić, czy dla danej liczby mieszkańców da się rozpisać tyle meczów? Próbowałem paru podejść i za każdym razem trafiałem na kontrprzykład, gdzie dało się uzyskać mniejszy wynik. Jakby ktoś mógł wyjaśnić, to będę wdzięczny :)

@kajak4u
Jeśli przez x oznaczymy łączną liczbę mieszkańców, a przez y sumę liczby mieszkańców na wcześniej pozycjach, chcemy teraz znaleźć minimalną wartość z(liczbę mieszkańców w i-tym budynku) dla której w budynku i będzie można rozegrać przynajmniej i meczów. Ten warunek można zapisać jako nierówność 3 stopnia. Żeby znaleźć takie z wystarczy przeiterować się do znalezienia takiego z(patrz wiadomości wyżej).