Ja mam 1.17s największy czas. Nie chciałem aby kod rozumiał wszystkie przypadki, bo k nie mogło być większe od 4, więc przeliczałem je na palcach, co nie wyszło takie straszne.

Pokażesz kod?

Dla każdego pola planszy zbadałem sąsiedztwo w odległości max. 4 pól i sumowałem wyniki, więc złożoność O(n^2). Dla 10d mam 2.96s.

Próbowałem różnych podejść, ale zawsze było trochę za wolno. Ostatecznie mam jakieś preprocessingi i bitsety, ale to i tak za wolne (na losowym maxteście minimalnie przekraczam TL, na nielosowym będzie gorzej).

Jak to się robi?

Działkę 2 [4B] dało się dość prosto zrównoleglić, stąd taki duży mój szacunek. No ale ogólnie mam wrażenie że trudniejsze zadania są w tym roku w sekcji [B], bo raczej poziom zawodników się aż tak nie obniżył ;).

;_;

haha, pierwszy

Nie potwierdzam czterech ostatnich testów czyli tych z k = 4. Moje outy:
60180190
38443472
246441536
536025811

Nie potwierdzam testów 12, 13, 14, 15, mam:
12: 60180190
13: 38443472
14: 246441536
15: 536025811

16 testów:
https://www.dropbox.com/s/pgm2225qmhdvvwc/cartests.zip?dl=0

Mi się długopis ostatnio wypisał :(

Jeśli z tych, którzy maja aktualnie max 13 punktów, mniej niż 120 przekroczy ten próg, to będzie rozdanych 380 koszulek?
Czyli byłoby -50% do prestiżu koszulki z tego roku.

Jest niemal pewne, że poczuli zapach koszulek i bruty dosłali.
Wcześniejsze Moz [3B] było trudne (<30 osób zrobiło), więc bardzo mało wiemy.

Brut na Działka 2 [4B] (czyli kod z netu odpalony na jednej instancji) dawał 1 punkt.
Carcassonne [5B] dla k<3 raczej tez przez wielu do zrobienia było/jest... 1 punkt?

Strzelam w puste pole z numerem 16.

No to ja mam chyba trochę prościej, aczkolwiek mi się w pierwszym i ostatnim 10000 kolumn średnio połowa instancji nudziła (na końcu może nie od razu, bo liczyły prostokąty, ale wcześniej zaczynały, więc to czekanie się przesuwało na zbieranie wyników).

Ja zrobiłem analogicznie. Nie wiem czy mamy takie same rozsyłanie w dół. Ja napisałem takie, że mamy log(liczba instancji) rund, w i-tej rundzie, rundy numerowane od 0, instancja id wysyła sumę prefiksową (w górę wliczając siebie) jaką zna do tej pory (na początku zna tylko swoją) do instacji id+2^i. Potem, każda instancja dla każdego z wierszy jej przypisanych, liczy prostokąty mające dolny bok w tym wierszu używając stosu i różnic wysokości pomiędzy prostokątami. Na końcu wszyscy wysyłają swoje wyniki do master instancji, która sumuje i wypisuje.

Jak zrobiliście zadanie Działka [B]?
Mi się udało zakodować następujące rozwiązanie:
Algorytm z dzi z oi9 zmodyfikowałem pod liczenie wszystkich prostokątów. Dane dzielę pasami poziomymi najpierw rozsyłając w dół głębokości (po 100 bo był limit na 1000 wiadomości), więc każda instancja zna głębokości z ostatniego wiersza poprzedniej. Potem dopiero liczę prostokąty zakończone w danym pasie drugi raz czytając poszczególne pola. Na koniec sumuję rozwiązania w jednej instancji. W sumie bardzo zwięzły i prosty kod wyszedł.
Złożoność O(n^2/i), czas max. 7.5s/12s, 10/10.