U mnie każda maszyna przetwarzała 100 wierszy na raz w jednej fazie, faz było max 8. Każda maszyna zapamiętuje sobie stan wysokości i stosów w 100 wierszach, co 750 kolumn przesyła wyliczony fragment do następnej i dalej liczy wiersze od góry na kolejnych 750 kolumnach.

5.20s / 12.00s

Też chciałem tak jak Paweł i wydawał mi się to fajny pomysł, ale jak się okazało że takie bezczelne przesłanie łańcuchem też siada to już kompletnie się rozczarowałem zadaniem :(

Liczę BFS-em odległość od już ułożonych płytek przez 4 warstwy. Dodatkowo dla każdej z płytek o odległości od 1 do 4 liczę ile ma sąsiadów o stopień niższych, równych i wyższych. Podczas tych obliczeń również agreguję wyniki, żeby wiedzieć np. ile jest płytek o odległości 2 do której przylega dokładnie jedna o odległości 1, itp.
Te obliczenia wstępne są w miarę lekkie.
Rozwiązania dla k=1 i k=2 są trywialne.
Dla k=3 rozważam 4 przypadki: 1-1-1, 1-1-2, 1-2-2 oraz 1-2-3, przez numer oznaczam warstwę w której znajduje się płytka. Oczywiste jest, że nie może być płytki z trzeciej warstwy, jeśli w drugiej nie ma żadnej. Np. dla konfiguracji 1-2-3 sumuję iloczyny dla każdej płytki o odległości 2, czyli mnożę ilość przyległych jedynek razy ilość przyległych trójek. Dla reszty robię sobie podobne reguły.
Dla k=4 tych przypadków jest już 8. Co ciekawe cztery te, które mają tylko jedną jedynkę są proste, ale najbardziej czasochłonne dla obliczeń. Oczywiście miałem też programik do brute-force'owania małych testów, który pomógł mi wygenerować 76 przypadków kontynuacji z tej samotnej jedynki, tzn. jeśli mam jedynkę, to obok niej muszą być 3 kolejne płytki o odległościach 2 lub większych. Możliwe kontynuacje, np. dwie w lewo i jedna w górę to te 76 kombinacji. Mówiąc dosłownie dla każdej płytki o odległości 1 odpalam sprawdzenie wszystkich 76 kombinacji i zliczam ile się udało.
Reszta możliwości to O(n^2) lub stała.
W zastosowanym podejściu kombinacja 1-1-2-2 to istne piekło, o którym pragnę zapomnieć.
Wracając do pytania o żyłowanie czasu. Poza tymi 76-ma kombinacjami to zwykłe przejście przez każdy element planszy. Czas niewiele większy niż wczytywanie danych. Żyłować można te 76 kombinacji, których sprawdzenie w najgorszym przypadku zajmuje ponad 75% czasu. Np. jeśli płytka z prawej nie pasuje, to można pominąć od razu wszystkie inne kombinacje, które jej wymagają. Zrezygnowałem z tego, kiedy zobaczyłem na uruchomieniu próbnym, że najgorszy przypadek działa w trochę ponad 3s. Żyłowanie bardzo mocno będzie zależeć od przyjętego sposobu na rozwiązanie. U siebie widzę kilka możliwości, ale pewnie nie znajdą zastosowania u innych osób.
Przez chwilę rozważałem przejście na maski bitowe, czyli zamiast tablicy char[] "..#..##." trzymać 00100110, czyli 72. Dalej przejść na maski dwuwymiarowe trzymane w jednej liczbie. Dla każdego pola można spakować 40 otaczających pól w odległości <=5 w 64-bitową liczbę, wtedy sprawdzenie jakiejkolwiek kombinacji byłoby operacją jednostkową.
Swoją drogą, ciekawe jak poszłoby rozwiązywanie dla k=5?

Korzystam z tego, że sytuacja się dzieje na planszy (a nie na dowolnym grafie). Generalnie pomysł mi przyszedł z metody liczenia pola wielokąta metodą trapezów - zamiast pola liczę tak ilości osad i w ten sposób będę sprawdzał czy jakieś osady zostały odgrodzone.

Utrzymuje spójne fragmenty warowni na planszy w postaci ich dowolnych drzew rozpinających, dla każdego wybieram dowolnie korzeń. Dla każdego pola/wierzchołka w takim drzewie trzymam "skierowaną" sumę ilości osad pod ścieżką (dosłownie pod polami na planszy) od korzenia do danego węzła (przez skierowaną rozumiem że dodaję gdy krawędź prowadzi do pola na lewo, bądź odejmuję gdy na prawo). W momencie dołożenia warowni, gdy łączy ona 2 różne drzewa to podłączam mniejsze do większego i przeliczam wartości na nowo. Natomiast gdy łączy 2 elementy z jednego drzewa to powstaje cykl - wtedy używam wyliczonych sum dla wierzchołków, które łączy nowa warownia by wyliczyć ile osad leży w środku i odrzucam zapytanie jeśli potrzeba. A gdy zaakceptujemy zapytanie (w cyklu nie było osad albo były wszystkie) no to merguję tę warownię z drzewem (cyklu nie robię, trzymam drzewo rozpinające).

edit: A no i do przesuwania osad trzymam sobie dla każdej kolumny wartości w drzewach Fenwicka o ile trzeba poprawiać sumy.

kurdę, jeszcze jutro wykłady mam na 8:00

Przysucha!

To ja chyba mam troszkę inaczej niż wszyscy i może nawet przyjemniej (4.19s na 10c po żyłowaniu) : (dla k = 4)
1.Liczę sobie odległości pustych pól od zamalowanych.
2.Zamieniam jedną jedynkę na zero (teraz będę liczył z tym polem wybranym) i poprawiam odległości, teraz w czasie stałym (!) liczę jaki jest wynik dla k = 3.
3.Wracam do poprzednich odległości (bez tej wybranej jedynki - ją zostawiam z zerem).
4.Powtarzam 2. i 3. dla wszystkich jedynek.
Wynik dla k = 3 w stałym to ta niefajna część rozwa: trzeba pamiętać liczbę jakichś takich kształtów: 1-2-3, 1-2-2, 1-2-1, 2-1-2, 1-2, 1 (to są odległości od zamalowanych pól).

My solution is to maintain the dual graph, so all cut operation becomes link operations in the dual graph.
And the only thing we need to check is if all the 'K's are inside/outside the circle when we try to link a circle in the dual graph.
For each 'K' we can give it a random value w[k] and shoot a ray to the right. Then let the value of a edge of the dual graph be the XOR sum of all rays intersect it. So the only thing we need to check is if the XOR sum of the value of the edges in the circle is equal to 0 or the XOR sum of all points. It can be maintained by using union-find sets.
And if the 'K' moves, we can twist the beginning of the ray and remain the right part unchanged. So there is only one unlinked edge changed its value in the dual graph per move.

Miałam jakiś zarys rozwiązania bazujący na tym: https://en.wikipedia.org/wiki/Dynamic_connectivity#General_graphs ale brakło mi czasu nawet na dokończenie pomysłu, nie mówiąc już o implementacji. Więc nie wiem nawet czy to dobra droga.

Też mam O(n^2) z dużą stałą i 4.86s na ostatnim teście (uff).

Ja dla k=4 zliczam takie kombinacje:
- 4 klocki w strefie tuż przy istniejącej figurze (dowolnie stykające się ale różne)
- jeden podwójny klocek z dokładnie jednym polem w strefie i dwa pozostałe dowolnie niedotykające tego jednego
- dwa podwójne z dokładnie jednym w strefie, niedotykające się (ok. 40% czasu wykonania)
- jeden potrójny z przynajmniej jednym ale nie wszystkimi w strefie i jeden niedotykający go
- jeden poczwórny z przynajmniej jednym ale nie wszystkimi w strefie (ok. 50% czasu wykonania)

Kraków!

Wpisujcie miasta startujące w Potyczkach! Warszawa!
Ja niestety w tym roku kiepściutko, pobugowało mi się trochę 83/120.
Ze znanych mi osób, których wyniki zdążyłem poznać:
1) Maciek Wawro 111
2) Mateusz Radecki 107
2) Marek Sommer 107
4) Kamil Dębowski 103
4) Krzysiek Maziarz 103
6) Jan Tabaszewski 93
7) Jarek Kwiecień 90
8) Wojtek Nadara 83

U mnie też wyszło sporo różnych możliwości i sporo kodu, dożyłowałem go tak że różne "klocki" (triomina i tetramina) trzymam na maskach bitowych, które potem ANDuję z odpowiednią maską na planszy. Podobne maski przygotowałem dla wszystkim domin i triomin razem z ich sąsiedztwem. 2.93s na 10d, ale udało mi się wygenerować testy które na SIO na uruchomieniu próbnym chodziły 4.8s :P

A jak poradziliście sobie z policzeniem wszystkich kombinacji (np. podwójny klocek i podwójny klocek to jakaś możliwość, ale trzeba uważać żeby nie były obok siebie, bo wtedy jest policzone już jako poczwórny klocek)? Ja jakoś sobie rozrysowałem wszystkie możliwości z włączeń i wyłączeń, ale wyszło sporo kodu (i 10s na maxteście niestety).

Czy ktoś kto zrobił OSA, albo ma jakieś sensowne pomysły, mógłby się nimi podzielić?