Ja też mam O(n^2), ze sporą stałą, na ostatnim teście 1.7s. Rozważałem przypadki: jeśli X to pola które na początku są sąsiednie do tego zamalowanego kształtu, to zastanawiałem się ile pól z X biorę. Jeśli na przykład bierzemy jedno, to nasz kształt jest takim spójnym k-polowym "klockiem" - generuje sobie wszystkie takie klocki na początku jakkolwiek i potem próbuje je przykładać na planszy. Pozostałe przypadki sprowadziły się do jakiegoś mniej lub bardziej prostego przejścia po tej tablicy i posumowania czegoś.

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.