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).

Dzięki :)
Prosta obserwacja, ale mi umknęła. I się zakopałem na drzewie przedziałowym do zliczania sumy uczestników na przedziałach oraz algorytmie próbującym wyznaczyć "gdzie należy zakwaterować kolejnego człowieka"...

Wpadłem na taki pomysł (chyba podobny) ale niestety nie zdążyłem do końca zaimplementować przed upływem czasu:

0. Opuszczam budynki bez gier bo tam nie musi być graczy.
1. Patrzę ile meczów jest w sumie (m) i szukam ile musi być co najmniej graczy (g): g*(g-1)*(g-2)/6 >= m.
2. Dla wyliczonej ilości graczy g tworzę teoretyczny ciąg ilości gier jakby każdy gracz był w osobnym budynku: (i-1)(g-i).
3. Próbuję zachłannie rozłożyć ten ciąg na mecze które są w kolejnych budynkach. Jeśli brakuje meczy to dodaję kolejne wyrazy tego ciągu. Jeśli widzę że ciąg jest krótszy niż ilość pozostałych budynków to kończę, zwiększam g o 1 i wracam do punktu 2.
4. Jeśli się udało rozłożyć ciąg, wypisuję g.

Czasy max 0.13s na lapku z Ryzen5.