@Marcin Smulewicz - jeśli ktoś nie był ani razu na finale, to 80 pts spokojnie mu wystarczy. Można było mieć cały weekend wolny, a i tak się dostać do finału :) Decyzja bardzo dobra.

W TEA łatwo można było ograniczyć liczbę porównań między blokami do połowy: na węźle i-tym blok i-ty porównujemy z blokami na lewo w odległości nieparzystej, a na prawo w odległości parzystej. To wystarczyło na 10pkt: max. 5.47s.

"Trochę jestem zawiedziony, że rozwiązanie liniowe dostaje TLE. To chyba nowość. Jak dla mnie słabe. Potyczki mikrooptymalizacyjne.

Wzorcowe rozwiązanie jest właśnie napisane na czas lepszy niż O(N). Brawa dla tych, którzy to zauważyli. Ale na dywizjon B takie cuda..." - nie bez kozery ta runda nazywa się ROZPROSZONA

Wracając do tematu wątku, mnie najbardziej podobało się zadanie RYK. Jeszcze go do końca nie wymyśliłem, ale już wiem, nad czym będę myśleć w wolnym czasie :)

GRA jest spoko. Na pewno fajnie by się oglądało te myślące jednostki. Najbardziej jednak podobało mi się to, że przy moim targecie nie musiałem jej pisać :)

Pamiętam kilka lat temu też było zadanie "gra", z pytaniem o wygrywającą stronę. Robiłem je kilka dni (pokonkursowo) i omal nie zwariowałem, tak było porąbane. Może nabawiłem się nawet urazu psychicznego do zadań o takiej nazwie. Tamto należało do A. To już chyba lepsza taka gra, jak teraz. Ale zdecydowanie bądźmy DRY i niech każdy nie pisze durnego wizualizatora. Może jakby był jakiś gotowy kod wizualizacyjno-testujący, "błędne rozwiązanie" :), to bym się zdecydował. (Sprawdziłem, zadanie jest z 2009 roku, opisane "W poszukiwaniu wyzwań").

Na IPSC w 2013 było zadanie typu gra. Tam wizualizator był w javascripcie. Tylko że tam wysyła się rozwiązanie, nie kod. Coś jak CodeJam. Ale jakby wsadem do wizualizatora było wyjście z naszego programu, to i javascript byłby ok.

Tak jeszcze w ostatniej chwili przyszedł pomysł do głowy: zadanie alternatywne. Z 2 zadań wybierasz 1 i tylko ostatnie zgłoszenie z tych 2 się liczy. Wtedy "gra" będzie tylko dla "graczy". :) Na dodatek dowiedzielibyśmy się, czy gra jest spoko. :)

No kurcze, wy chyba nie wiecie co to jest opty. Tutaj nie trzeba było żyłować rozwiązania do granic i konkurować z innymi, tylko mieliśmy daną z góry ustaloną przez jurorów granicę i trzeba było do niej dojść, co nie było trudne, jurorzy nie wymagali dużo. Oczywiście w tym zadaniu byłoby pole do popisu, ale było raczej zadaniem na w miarę sensownego zachłana i sprawdzenie czy umiesz napisać kawałek kodu, co w konkursach jakoś zazwyczaj idzie w parze z myśleniem (jak to powiedzieli organizatorzy przedostatniego CERCA w Pradze - "To są zawody z programowania, a nie z matematyki teoretycznej" - nie no, tutaj to żarcik). Ja byłbym przeciw co do opty-opty, to faktycznie nie klimat potyczek, ale zadanie tego typu moim zdaniem było bardzo dobre. To, że pierwsza rzecz którą napisałeś działała, w ogóle mnie nie dziwi, miałem tak samo, co potwierdza, że limity narzucone przez jurorów nie były ciasne, a samo zadanie było prostawe (i powinno, w końcu było w B).

I: tak, trochę oklepana tematyka, ale tym bardziej było prostawe przez to. Jak dwa lata temu puszczałeś flowa po raz setny, a rok temu pisałeś centroidy to nie marudziłeś, konkursy trochę tak działają, jak coś już umiesz to Ci łatwiej, tylko mniej fajnie się pisze. Mogło być gorzej, mogli chcieć żebyśmy ruszali jednostkami po planszy, które dostarczają przesyłki, mają swoje pojemności, a przesyłki mają limity na czas dostarczenia...

Co do GRA no to rozumiem, że może i takie zadania się niektórym podobają, bo czy se tam mogą pooglądać własne wizualizacje, czy coraz bardziej poprawiać własne pomysły i mieć z tego fun. Akurat w moim przypadku napisałem pierwszą nieidiotyczną rzecz, która mi przyszła do głowy i po usunięciu małych bugów praktycznie od razu działało, czołgi się od razu wyrabiały z ogromnym limitem, a farmerzy na polu bez kamieni dawali ~400 ruchów i jedyne co mi było z tego całego funu to patrzenie na sumaryczną liczbę ruchów, bo nic więcej mi nie było potrzebne w zasadzie. Jedynie ręcznie kilka razy musiałem sobie wypisać planszę i zobaczyć czemu na tym jednym na kilkaset ostatnich testów się zdedlockowało i dodać jakiegoś głupiego fixa aby się tak nie działo.
Ja się w takowe nie bawię, ale w Internecie jest chyba sporo konkursów zarówno optymalizacyjnych (topcoderowe marathony) jak i takich gdzie trzeba pisać jakieś pseudosztuczne inteligencje do jakichś botów grających w jakieś gierki. Jest to niewątpliwie jakiś skill i jakiś rodzaj zabawy, ale nie widzę powodu, czemu zwolennicy takich rozrywek po prostu nie znaleźli innych miejsc, gdzie mogą się pobawić takimi rzeczami, a Potyczki zostawić czystymi od takowych, bo zdecydowanie takie zadanie nie pasuje formą do nich.
Do tego jeszcze skomentuję to, że może rzeczywiście _coś_ w tym zadaniu trzeba pomyśleć i zmierzyć się z pewnymi problemami jak np. wspomniane
"- kiedy dokładnie odnosić złoto do bazy? Na początku trzeba szybko żeby budować nowe jednostki, później trzeba z tego zrezygnować i zebrać złoto z drugiego końca planszy.
- co zrobić na koniec, gdy wszyscy odnoszą złoto, aby się nawzajem nie zablokowali?"
ale oba wydają mi się dość nudne i przyziemne w porównaniu do reszty zadań z PA. Zadanie zdecydowanie bardziej na klepanie setny raz "z każdej jednostki zapuść bfsa i w jakikolwiek nieidiotyczny sposób wybierz jej następny cel i tam idź" niż jakieś ciekawe podejście. Już nawet zadania optymalizacyjne, gdzie się jakoś sensownie przeszukuje przestrzeń rozwiązań, zapuszcza jakieś beam searche, local searche, genetyki, NMCSy, MCTSy, czy inne tego typu rzeczy są dużo ciekawsze i można się w nich wykazać dużo większą pomysłowością niż w czymś, gdzie zdecydowanie głównym problemem jest przeniesienie trywialnych idei na 500 linijek kodu tak aby nie umrzeć.
Bardzo bym nie chciał aby zadania tego typu zagościły na dobre w PA i bardzo bym nie chciał jakiejś rundy optymalizacyjnej, pomimo tego, że nie jestem takim przeciwnikiem tego typu zadań na jakiego się wydaje po napisaniu tego posta i lubię sobie od czasu do czasu wystartować w jakimś Deadline24 czy napisać jakieś opty, ale po prostu nie zanieczyszczajcie tym Potyczek :P.

Ta, też chciałem o tym wspomnieć, w pełni zgadzam się z Wojtkiem.

To ja lekko zbaczając z tematu w obronie wspomnianego HER wspomnę, że to zadanie wcale nie jest z gatunku "napisz byle co i zobacz, że działa" tylko zupełnie legitnie używając mądrych słów projektujemy branchingowy algorytm typu Las Vegas (tzn. zawsze działa poprawnie, ale jak ma pecha to będzie działał długo, ale to się dzieje z bardzo małym pstwem) z bardzo konkretną oczekiwaną złożonością czasową. Oczekiwana złożoność czasowa się dowodzi i wynosi O(sqrt(2m)^((k+1)/2)), a jak się doda jakieś opty to nawet można zbić to O(sqrt(2m)^k / k!). Nie nazywałbym tego "heurą".

Mi przyszedł do głowy jeszcze jeden argument: format finału i format eliminacji (potyczek) to i tak dwa całkiem różne światy, więc nie widzę problemu w jeszcze drobniejszym odbiegnięciu.

Postaram się to zrobić dzisiaj w nocy. Jednakże proszę mieć na uwadze, że zadania rozproszone tam nie trafią.

Sortujesz półproste kątowo i tworzysz przecięcie na stosie (algorytm w pewnym sensie podobny do algorytmu konstruowania otoczki wypukłej), pilnując, żeby przecięcie dwóch poprzednich półprostych leżało po lewej stronie tej dokładanej. Na koniec trzeba jeszcze zapleść początek z końcem, żeby się wszystko zgadzało.

Tak swoją drogą, czy ktoś rozważał zaprzęgnąć podejście AI do tego zadania, np. Q-learning? Czy to miałoby jakiś sens?

Nie, ten dwuwymiarowy dynamik się przydawał tylko do preprocessingu czwartego (i w małym stopniu też trzeciego) podzadania. W subtaskach 1, 2, 3 korzystałem z metody prawie identycznej z tą napisaną przez Ciebie.

Dla mnie GRA była bardzo fajnym urozmaiceniem. Mimo iż w moim przypadku zakończyło się totalną klapą w związku z brakiem czasu, to miałem z jego klepania i debugowania najwięcej przyjemności.

Natomiast rozumiem, że wielu osobom zadanie mogło się nie podobać, bo nie da się ukryć, że zmienia charakter konkursu. Pewnie organizacyjnie byłoby to nie do przeskoczenia, ale dla mnie idealnie byłoby gdyby był osobny konkurs z jednym zadaniem typu GRA (może trudniejsze, a może turniej programów walczących jak za dawnych lat w ITPW) i tydzień czasu na jego rozwiązanie :)