Edit: Tak właśnie. :)

Ach, wybacz. Źle zrozumiałem. (Znaczy, wiedziałem, że masz inny algorytm, ale <cut>... w ogóle źle zrozumiałem z tą listą)

> Rozproszone zadania były super, ale trzeba popracować nad powtarzalnością sprawdziarki (no i Wam też zabrakło mocy
> obliczeniowej pod koniec rundy rozproszonej). Fajnie by było też gdyby koszty komunikacji/synchronizacji były lepiej
> udokumentowane.

Fajnie by było, gdyby API udostępniało nonblocking receive ;)

> Ale to są tylko pomysły. Ogólnie było oczywiście bardzo pozytywnie i bardzo udane! Dziękuję za świetną zabawę.

Popieram i też dziękuję.

PS
Widzę, że z regulaminu znikł punkt o udostępnianiu rozwiązań. Szkoda,
to była dobra szkoła analizy cudzych kodów :)

Moim zdaniem podział na A/B jest ok, bo, poza kwestiami z koszulkami i rankingiem tylko-B, jest dodatkowym narzędziem w rękach organizatorów, aby podpowiedzieć uczestnikom, jakie rozwiązanie jest oczekiwane. Przykłady:
1. w ostatniej rundzie MUZ było chyba łatwiejsze niż PLE (a na pewno niż PLE w O(n log n)), więc fakt, że PLE było B (i te 1024 MB) był sygnałem, że będą przechodzić powolne rozwiązania. (Chociaż fakt - mogliby zrobić, żeby brut n^2 nie wchodził :) ).
2. w rundzie rozproszonej było tak, że widać (przy odrobinie obycia), że można zrobić KOL w O(n log n / m) w naturalny sposób, ale żeby uzyskać czas O(n / m), trzeba bardziej pokombinować (przynajmniej jeśli chodzi o skomplikowanie implementacji), tzn. dolosować więcej punktów. Fakt, że to zadanie było B, był sygnałem, że nie trzeba tego robić. Gdyby SEK było B a KOL było A, to uznałbym, że może to być wymagane.

Edit: A, rozumiem, dzięki. Dzięki temu że masz kopiec kolejek reakcji, a nie kopiec reakcji, sumaryczny czas to O(n log m). Ma to sens. Rozwiązanie Kamila chyba działa w O(n log^2 m).

Ja miałem inny algorytm, u mnie kolejność reakcji na liście nie ma znaczenia. Liczę LCA dla każdej reakcji metodą Tarjana, więc chodzę po drzewie i jak dojdę do liścia to potrzebuję wiedzieć dla których reakcji mam policzone LCA.

Czy ktoś może miał problem z testem 3b? A jeśli tak, to gdzie tkwił błąd? Bo godzinami mogę wpatrywać się w swój program, pisać małe testy poprawnościowe i wciąż WA. Tu miałem 9/10, dlatego z ciekawości interesuje mnie ten jeden test na trzeci punkt :)

Tomek Czajka: Kolejka zachowuje kolejność. Z Twojego opisu wnioskuję, że pełniły one tą samą role, co u Ciebie. Kamil do zachowania kolejności używał seta, a ja kolejki. Z tym, że u mnie w fiolce trzymany był kopiec kolejek, dlatego nie musiałem w żaden sposób ingerować w elementy w obszerniejszej fiolce (poza aktualizacją kopca, ale to wykonuje się w czasie logarytmicznym względem liczby kolejek w fiolce*, a ponieważ wtedy, kiedy można było owe kolejki łatwo scalać, czyli podczas przepisywania, scalałem je to tych kolejek nigdy nie było wiele). Nie przepisywałem też tych, których nie potrzeba. Tak jak wspomniałem, nie ruszałem elementów zbioru większego poza momentem, w którym dodawałem nową kolejkę do kopca. Ale kopiec był kopcem wskaźników na kolejki, zatem nie było tutaj problemu z kopiowaniem. Dodatkowo zawsze do kopca dodawałem tylko jedną kolejkę, ponieważ jak wcześniej napisałem, podczas przepisywania elementów ze zbioru do zbioru, scalałem je.
Ale ogólnie przyznaję, użycie kolejek było błędem. Przyszedł pomysł na nie jakoś na początku i tak bezrefleksyjnie pozostał. Niestety nie pomyślałem o zamianie ich na coś innego.
*Tak zakładałem pisząc program, ale teraz widzę, że set znacznie poprawia wyniki czasowe.

Ja trzymałem moje listy tak: w każdej fiolce mam wskaźnik do pierwszej reakcji w której dana substancja ma uczestniczyć, w każdej reakcji mam wskaźnik do następnej. Tak samo chyba można trzymać te kolejki.

Nie rozumiem tylko: czemu kolejki? Czy coś jest z nich usuwane? Rozwiązanie Kamila wymaga chyba tylko dodawania (niekoniecznie wszystkich) elementów z mniejszego zbioru do większego zbioru, i kasowania całego zbioru.

Ja dokładnie tak robiłem :) I mam 6/10 przez TLE dla k=5.

Nie byłem fanem podziału zadań na A i B.
Niech sobie zawsze będzie prostsze i trudniejsze - to popieram.
Ale uważam, że nie powinniśmy wiedzieć które to które.

To że SEK było B to był błąd. KOL było trudniejsze.

Oddzielny ranking dla B też chyba nie spełnia żadnej roli.
SEK[A] łatwiejsze od KOL[B], MUZ[A] łatwiejsze od PLE[B].

Można by ranking B robić z Suma_po_rundach(Minimum(Punkty uzyskane za zadania na rundę, Połowa punktów za rundę)) jeśli już trzeba.

To że PLE było B chyba spowodowało, że tam było tak dużo pamięci i tak wysokie limity czasowe. W tym zadaniu można było spokojnie liczbą punktów porozróżniać trochę różne złożoności.

Ogólnie nie jestem fanem testów.

W PAK było za małe rozróżnienie złożoności.

W PLE było za dużo testów poprawnościowych a za mało rozróżniających złożoność. Miałem przyzwoitą złożoność ale z dużym bugiem, na losowych testach prawie zawsze działało, a tu mi przeszło tyko na jeden punkt. A tu podobno N*N dawał 10/10.

Ogólnie trochę żal, że tylko 10 punktów za każde zadanie, że punkty było 0 albo 1 (bez frakcji za ponad połowe limitu czasowego etc) i że nie było więcej rywalizacji z przeciwnikami.

Coś w stylu: zadanie z 10ma paczkami po 10 testów. Spośród rozwiązań poprawnie rozwiązujących daną paczkę rozwiązanie z najlepszym czasem T dostaje 10 punktów. Do 125/150/175/200/...% T inni dostają 10/9/8/7/... punktów.

Mogłoby też być jakieś zadanie bez optymalnego rozwiązania gdzie się dostaje X sekund, żeby zastosować heurezy i wypisać najlepsze znalezione.

Nie było też żadnej gry.

Rozproszone zadania były super, ale trzeba popracować nad powtarzalnością sprawdziarki (no i Wam też zabrakło mocy obliczeniowej pod koniec rundy rozproszonej). Fajnie by było też gdyby koszty komunikacji/synchronizacji były lepiej udokumentowane.

Ale to są tylko pomysły. Ogólnie było oczywiście bardzo pozytywnie i bardzo udane! Dziękuję za świetną zabawę.

To jest w sumie całkiem dobre pytanie. O ile różnych miejsc dla programistów w sieci jest bez liku (fora, strony, Q&A, kanały IRC) to osobiście nie znam niczego sensownego dla algorytmików. Zostają tylko książki i materiały dla studentów (np. świetne materiały UW) czy ewentualnie blogi. Nie jestem pewien, czy w polskiej części sieci istnieje jakieś żyjące forum dla osób zainteresowanych tą tematyką. Aczkolwiek może to wynikać z braku zapotrzebowania na nie.

A czy ktoś robił tak, że sprowadzał problem do przypadku n <= k! (czy tam k!/2) wyżej opisaną metodą, a potem rozwiązywał go programowaniem liniowym z jakimś zaokrąglaniem wyniku (do liczb całkowitych)? Pytam, bo nie wiem, czy straciłem jakieś punkty na nienapisaniu tego ;)

Ja mam tylko jedną uwagę odnośnie SIO2, brakuje mi opcji wyszukiwania w rankingu, która była dostępna na starej stronie :)

Większość robiła LCA. Cześć tradycyjnie, ktoś offline Tarjanem.
Dominik, który miał problem z pamięcią, robił to bardziej bezpośrednio.

>Przejrzałem w sumie ranking i doszedłem (na oko) do ciekawego wniosku:
>tak mniej więcej w Top60 ludziom bardziej wchodziło [A], zaś poniżej Top60 [B]. Ktoś może się domyślać, czemu? :P

Zapewne ludzie w czołówce są obeznani ze standardowymi algorytmami, takimi jak liczenie odległości edycyjnej. Ci dalsi albo ich nie znali, albo nie implementowali, i mogło im być trudniej wyobrazić sobie tą dwuwymiarową tablicę, i jak obliczanie jej zrównoleglić. Ponadto dochodzi fakt, że ludzie w czołówce na pewno bardziej patrzą na ranking A+B, a reszta skoro i tak się nie załapie na finał, to nieco sobie daje luzu na zadaniach z A, i skupia się na B, żeby chociaż koszulkę wygrać. Oczywiście nie mówię, że wszyscy tak robią, ale statystycznie jest to prawdopodobne ;)

@Bartłomiej
Jeżeli podział przechodził przez prostokąt, to dopisywałem go do dwóch dzieci. Później jak ilość elementów się zmniejszała poprzez usunięcie kolidujących, to wracając także musiałem sprawdzać, czy prostokąt z liści nie jest tym samym. Oczywiście funkcja szukająca punktu podziału była taka, aby unikała dużej ilości przecięć z prostokątami.