Dla mnie pisemne rozwiązania zadań są zwykle lepszym wyborem - i dlatego cieszę się z omówień dla B. Także dzięki za nie! Co do A, pewnie idealną formą byłoby film+pdf. ;) Z realnych sugestii - w miarę możliwości sugeruję używanie białych tablic (i piszących piasków), na tych kredowych na filmach czasami przejrzenie się rysunkom czy rozróżnienie kolorów bywa problematyczne.

Mi też podoba się Bilard. Sztuka programowania polega na tym, żeby rozwiązanie nie było "syfne"! Akurat ja z mojego wysłanego rozwiązania nie jestem pod tym względem szczególnie dumny, ale potrafię sobie wyobrazić, jak mogłem je ładnie zaimplementować :)

Swoją drogą w Grzybach, podobnie jak w Bilardzie, też mam gorszą złożoność, O(n log^2 n). Liczę sobie otoczkę wypukłą, i uaktualniam ją w czasie O(log^2 n) po każdym kroku. 8 punktów.

Rada na przyszłość: warto było przetestować porównując wyniki na małych n z prostszym, wolnym rozwiązaniem.

Akurat Hilberta nawet całkiem dobrze mi się klepało, ale to chyba kwestia tego, że znalazłem fajny sposób na przelanie idei w kod. A początkowo, jak wymyśliłem rozwiązanie, to byłem przerażony i rzeczywiście myślałem, jak straszny syf to będzie, ale spędziłem trochę czasu nad upraszczaniem tego i wyszło "tylko" 170 linii :)
(Tym bardziej smutny byłem, jak zobaczyłem to 0, bo byłem szczerze dumny z mojego rozwiązania)

Cóż, ja miałem rozwiązanie polegające na rekurencyjnym rozpisaniu tego, jak wygląda odbijanie się między dwiema sąsiednimi krzywymi Hilberta dla każdej możliwej konfiguracji, a potem sobie na podstawie tego jakoś obliczałem, jak wygląda odbijanie się w oryginalnym zadaniu, i bug właśnie nie znajdował się w rekurencji (gdyby tam się znajdował, to prawie na pewno wszystko by się sypało), tylko właśnie w tym ostatecznym wyliczaniu. Moim zdaniem w tym zadaniu testy losowe wystarczyłyby, bo nie jest heurogenne, tylko przypadkogenne i w dodatku rekurencyjne. Jednak nie dziwię się, że układający testy miał pokusę dania przypadku szczególnego :P

Lucjan: jeśli zadanie jest dla zawodowców, to taki zawodowiec też musi trochę czasu nad nim spędzić. ;-)

Anna: dzięki za sugestię. Faktycznie filmy były podzielone na części, które nawet miały swoje robocze nazwy, ale nie opisaliśmy ich publikując. Weźmiemy to pod uwagę w przyszłości.

Patryk: Takie "Making of" nie ma racji bytu. Musielibyśmy udawać, że zaczęliśmy pracować nad drugim dniem Potyczek przed tym, jak Wy zaczęliście pracę nad pierwszym. ;D

A tak serio, to byłby to bardzo krótki film. Dosłownie kilka sytuacji przy nagrywaniu omówień. Poza tym, to się siedzi z herbatą i pisze algo.

O wpadkach informowaliśmy przez dział pytań. Sukcesem jest zadowolenie uczestników.

Z promocją w pełni się zgadzam. Masz jakiś pomysł na realizację?

Może obok omówień zadań, na podsumowanie Potyczek można przygotować coś w rodzaju "Making of" z relacją z przygotowywania zadań, o całym procesie wymyślania, udowadniania, testowania. Ktoś pewnie czuwa nad stroną sprzętową, ktoś jest na bieżąco z forum, ktoś coś jeszcze innego? Wpadki? Sukcesy? :)
Co do zadań, widzę że Hilbert budzi mieszane uczucia. Pozwolę sobie zauważyć, że to zadanie, niby z 5 rundy, ale które można zrobić bez solidnego akademickiego przygotowania.
I jeszcze promocja Potyczek, mam wrażenie, że idea i forma mają ogromny potencjał. Myślę, że warto położyć większy nacisk na ten aspekt.

Kiedy kolejne? :)

Omówienia zadań z grupy B w postaci pdfów = REWELACJA.
Wreszcie po latach się doczekaliśmy :)
Wiem, że to kosztuje mnóstwo pracy,
ale moim zdaniem naprawdę warto.

Co do rozwiązań z grupy A filmik pewnie wystarczy...
Wyobrażam sobie, że zawodowiec zerknie tylko,
przecież nie będzie oglądał 15 minut, skoro 2 min wystarczą :)
i już zna rozwiązanie.

Serdecznie pozdrawiam organizatorów
Lucjan

Bilard robię tak:

1. Liczę dla każdego n, kiedy dojadę do każdego rogu. Przy czym liczę czas na 3 sposoby: zegarek włączony cały czas, zegarek włączony tylko po parzystych odbiciach od brzegu, zegarek włączony po nieparzystych odbiciach od brzegu.

2. Funkcja BorderHit, która dla danego n,k liczy czas do k-tego odbicia od brzegu. Znowu liczy czas na jeden z trzech sposobów. Ta funkcja działa w O(n).

3. Główna rekurencyjna funkcja, która rozwiązuje podane zadanie. Najpierw, używając obliczonych czasów dla rogów znajduję, wzdłuż którego z 16 segmentów długości połowy boku będę jechał w danym momencie. Przy czym czas przejazdu przez segment w środku liczę jako sumę dwóch czasów: po jednej stronie czas spędzam po parzystych przejazdach, po drugiej po nieparzystych.

Jeśli ten segment jest jednym z ośmiu na brzegu kwadratu, to wywołuję się rekurencyjnie.

Jeśli jest jednym z ośmiu w środku, które jadą pomiędzy dwoma mniejszymi kwadratami, to wtedy wyszukuję binarnie, ile razy przechodzę przez linię środkową, używając funkcji BorderHit. Czas spędzony po jednej stronie jest po parzystych przejazdach, a po drugiej stronie po nieparzystych. n wywołań funkcji O(n), czyli ten krok jest O(n^2).

Jak już się dowiem, ile razy przechodzę przez linię środkową, to wtedy wywołuję znowu całą funkcję rekurencyjnie po odpowiedniej stronie, odpowiednio poprawiając pozostały czas jazdy na taki, jaki byłby gdybym odbijał się tylko po tej stronie (znowu funkcja BorderHit).

Razem: O(n^3).

Pomogłem sobie tablicując najpierw wartości funkcji BorderHit dla n<=16, co kilkukrotnie przyspiesza. Przechodzi ostatni test w 1.24/2.00.

Prawdę mówiąc, to myślałam, że omówienie wideo jest bardziej czasochłonne. Jeśli nie, to dziwi mnie, że nie były obie grupy w formie wideo.

Co do checkpointów, to pisałam to na podstawie moich obejrzeń omówienia do reorganizacji (czy wzorcówka jest tak samo skomplikowana jak mój pomysł) i grzybów (jak daleko byłam od rozwiązania) i w obu potrzebowałam około 2 minut.

A co do samego istnienia omówień to bardzo mnie one cieszą i moje drobne uwagi tego nie zmieniają.

Auuuu. Boli. Można gadać, że Twoja wina i że ktoś kiedyś też miał smutno, ale chyba nikt nie powie, że to sprawiedliwe. Na Twoim miejscu też na pewno byłbym rozgoryczony :P.

Kwestia jest taka, czy osoba przygotowująca testy była świadoma, że to dla jakichś rozwiązań może być jakiś przypadek szczególny. Dla mnie osobiście nie wygląda on w żaden sposób inaczej niż cała reszta i puściłem rekurencyjnego checka w swoim rozwiązaniu po całym przedziale [0, 2^(2n+2)), więc jakbym przygotowywał testy, to bym się nie zastanawiał nad wymiarem kary dla osób źle rozpatrujących ostatni punkt na trasie. Co za tym idzie, dość możliwe, że przygotowałbym testy, w których nie zwracałbym uwagi na obecność tego punktu i być może znalazłby się on we wszystkich testach, być może w części, a być może w żadnym. Sądzę, że more or less takim tokiem rozumowania szła też osoba przygotowująca testy i "tak wyszło", że się znalazł wszędzie. Nikt raczej świadomie by 10 pkt nie urąbał za złe rozpatrywanie jedynie tego punktu (no chyba, że jego nazwisko zaczynałoby się na "Dąb", a kończyło na "owski" :P).

W każdym razie obstawiam, że 85 pkt starczy na finał, więc raczej nie będzie aż takich powodów do rozpaczania :P (pamiętajmy o osobach z zagranicy i o tych, które zrezygnują).

Zgadzam sie z Anną, rzeczywiście udane Potyczki, brawa dla organizatorów.

Osobiście najbardziej lubię kombinacje cech zadań (fajne, trudne) i tutaj Grzyby i Pokrycia się bardzo dobrze spisały, ale (fajne, <=średnie+) też chętnie przyjmę i tu wrzucam 1A, 2A, 3B i CNF :). Natomiast najbardziej nie lubię kombinacji (syfne, trudne), do której zdecydowanie wpada Bilard Hilberta - obecność tego zadania to moim skromnym zdaniem jakaś tragedia okrutna.

Ja osobiście wolałbym, aby omówienia A zostały w formie wideo. Jestem przekonany, że oboje pisaliście jakieś opisy wzorcowych algorytmów do niebieskiej książeczki, czy inne prace i jesteście świadomi, ile czasu to zajmuje. Ja ostatnio pisałem 3 rozwiązania do bluebooka i nawet w prostym zadaniu zajęło mi to z 6h. A wyobraźcie sobie ile by zajęło spisanie tekstem takich palindromów :d. Poza tym jednak jednak rzadko jest tak, że się nie wie jak zrobić zadanie, a z 15 minut starczą 2, aby zrozumieć czego brakuje. Nawet jeżeli zabraknie bardzo mało, to autor będzie pewnie używał innych notacji itd. i i tak trzeba by obejrzeć przynajmniej większosć. Aczkolwiek jakieś checkpointy na tych omówieniach rzeczywiście mogłyby być dobrym pomysłem tylko pewnie często ciężko będzie je sensownie sformułować, to może być zależne od zadania. No i przypomnę, że kiedyś nie było żadnych omówień, a oficjalne omówienia do B chyba są po raz pierwszy.

A co do formy omówień zadań B jestem neutralny.

@Tomek: Bilard w O(n^3)? I do tego jeszcze taki, który wszedł :D? Ciekawe. Wiem o istnieniu 3 rozwiązań (swoje, Soko i z omówienia) i wszystkie trzy są istotnie różne i wszystkie działają w O(n). Jak chciałbyś opisać ideę, to chęnie przeczytam, ale bez wchodzenia w szczegóły, bo byłoby to to pewnie bolesne i dla Ciebie i dla czytających :P.

Ja dzieliłem sobie tor lotu piłki na ~12 przypadków, na których bieg zachowywał się tak jak bieg na jakiejś mniejszej krzywej modulo pionowe złączenie wewnętrzne i zewnętrze, gdzie trzeba było jeszcze dopisać proste ify. Czasy, w których zaczynały się dane odcinki toru brałem z bruta dla małych wartości n i zgadywałem zależności, które je dawały dla większych n.

W sumie wymagało to ode mnie a) napisania bruta (~1h), b) głupiego gapienia się w krzywą rzędu 5 i 6 z Wikipedii przez 3 bite godziny, c) kodzenia wszystkich przypadków, wyciągania zależności itd, oczywiście także co chwila spoglądania na krzywą (~5-6h) i wyszedł mi z tego chyba najbardziej absurdalny kod jaki w życiu napisałem.