Wydaje mi się, że zadania C mają przy okazji charakter edukacyjny, więc całkiem fajne jest pokazanie zadania, które może być rozwiązane właśnie tak, że piszemy wolny program, z którego wyniku możemy skorzystać we wzorcowym rozwiązaniu. Jak się to zna to wydaje się oczywiste, ale jeśli ktoś to zobaczył po raz pierwszy to myślę, że fajna lekcja.

Też żyłowałem O(n^2) do piratów i przeszło pod limitem wszystkie testy (5.53s/6s najgorzej). Dostałem 6 o dziwo przez głupie WA, które da się łatwo naprawić nie ruszając bottlenecka, więc z fixem prawdopodobnie dostałoby 10

Dzięki sprytnym optymalizacjom piraci O(n^2) mogą zostać zoptymalizowani do 7 punktów, a prawdopodobnie przy dalszym dopracowaniu można osiągnąć 10 punktów (nie przeszło 3 testów z limitem czasu). (Ja tego nie zrobiłem, ale mój znajomy BLOBVISGOD używał takiego podejścia).

@Yahor, co do tego 5e4 to jeśli wzorcówka O(nsqrt(n)) w EGZ, czy O(n log(n) K log K) gdzie K to to ograniczenie na chciwość w PIR, czy O((k+q)log(k+q)) w ZBI ma dużą stałą, to nie chcemy dawać n=5e5 i TL=doba bo sprawdzaczka tego nie przeżyje przy liczbie testów potrzebnej by uwalić wszystkie błędne rozwy, dajemy z grubsza najmniejsze n, przy którym czujemy się bezpiecznie, że brut typu O(n^2) jest bez szans, jak to będzie coś koło 50,000/75,000 to nie widzę w tym większego problemu zwłaszcza jak masz test-runy, jak zastanawiasz się, czy O(n^2) ma szansę przy n=50000 po prostu naklep, wrzuć na SIO z jakimś testem, który mniej więcej wybija maksymalny czas i zobaczysz, że niespecjalnie ma

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.

@burro: w takim systemie by moim zdaniem zadania się jednak marnowały: celując w finały nawet bym nie czytał zadań B i C, a w koszulkę czytałbym tylko B. I tylko dołożył starań, żeby mieć na pewno 10 na tym zadaniu. Poza oczywiście sytuacją, że przez większość dnia nie umiem wymyślić tego zadania powiedzmy A na 10 i na A wrzucam bruta, i dopiero wtedy robię to B. Ponadto czy to takie złe, że osoba celująca w finał musi spróbować podejść do wszystkich 18 zadań (tym bardziej, że próg zazwyczaj leży w okolicy 13-14 zadań)? Trochę tak, jakby na Codeforces zawodnicy 2400+ mieli zadania A i B w div1 automatycznie zaliczone jeśli wrzucą C.

Nie wiem czemu ludzie dali tyle minusów pod Twoim pomysłem, warto dyskutować.

Dziękujemy za propozycję zadania o Bajtazarze startującym w potyczkach w nowej formule, ale niestety zdążyłeś to zadanie spalić pisząc o nim na forum 😂😂😂

@Albert
I co by Ci dała taka tablica bitów z całą planszą? Pomijając ogromne straty na czas alokacji i dostępu do takiego molocha, to już chyba serio lepszy set<pair<int, int>>. Z resztą ja w brucie na 5p utrzymywałem planszę jako graf, gdzie wierzchołki "zapominają" swoją lokację i masz normalną tablicę sąsiedztwa (pamiętany jest kierunek NWSE), a map<pair<int, int>, int> mówi jakie id wierzchołka jest przypisane danemu polu i jest updateowane raz na query. Więc literalnie tablica bitów na całą planszę to jest wręcz zaszkodzenie sobie.

Co do komentarza do MIG to się nie zgadzam: nie wszystkie zadania na konkursie algorytmicznym muszą się wiązać ze skomplikowanym kodowaniem, wręcz imo ważniejsza jest ta część koncepcyjna (która czasem się odwołuje do użycia znanych technik programistycznych, np. bitsetów żeby mieć złożoność O(coś/64)). To że zadanie nie ma inputu, to nie jest żaden problem, bo bardzo łatwo by było go na siłę dodać (np wczytaj dwie liczby n, k i wypisz planszę o rozmiarze nxn osiągajacą score k, i napisac w opisie testów, że i-ta grupa ma n = 100, k = (10i - 1)^2).

Co do AKW: trudno by było zapewnić brak stablicowania. Gdyby np było n <= 10 000, możnaby stablicować odpowiedzi dla tych większych n, które jeszcze się mieszczą w limicie na rozmiar kodu, a małe n brutem liczą się szybciej. n istotnie większe od 10 tys znacząco komplikuje rozwiązanie w stosunku do docelowego zliczania wartości a^2 + b^2 oraz k^2 - h^2.

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

też niechcący najpierw naklepałem trudniejszą wersję xd Wujkowi Nadarze to pewnie 7 minut straty daje. Ja tam całe popołudnie do kosza se wyrzuciłem 🫠

Chyba ciemne tło -> zaznaczył że nie może lub nie chce brać udziału w finale.

Co do nowego rankingu, to może ja jestem stary jak ten stary ranking, ale czysto estetycznie stary ranking mi się bardziej podobał. Natomiast info o cutoffach na top-10 / top-20 jest super.

#92616 rozważaliśmy to gdy wprowadzaliśmy C, ale doszliśmy do wniosku, że przez to, że C jest odsłaniane, to i tak nie wymaga ono wysiłku od zawodników celujących w finał (nie trzeba poświęcać czasu na np. pisanie bruta czy upewnianie się co do poprawności rozwiązania).

Przecież się nic nie zmarnowało

A może ranking B + C (koszulki) oraz A + B (finał)?
Duża część pewnie i tak zrobi wszystkie zadania, bo i fajnie się dostać do finału i fajnie koszulkę zdobyć, a osoby mające mniej czasu będą mogły się skupić na jednym rankingu.

[MIG] - czy to jeszcze programowanie? Po napisaniu inputu dla visualizera, wystorczyło go wyprintować. Równie dobrze moglibyśmy wysyłać pliki .in...
[AKW] kusiło mnie ztablicować wyniki. Zgadzam się, że za hardcode rozwiązania nie powinno wpadać 10 punktów
[ZBI] limit pamięci był tak duży, że można było normalnie zrobić sobie tablicę bitów z całą planszą, która mieściła się w pamięci (625e6 bajtów).