Czy mógłby ktoś podać poprawne rozwiązanie zadania fiolki, dziękuję.

1. Dla każdego kubełka (czyli substancji) tworzymy 'listę oczekiwań', czyli seta z numerami reakcji, w których dany substrat bierze udział. Set w celu posortowania.
2. Wykonujemy kolejne kroki symulacji. W każdy kroku łączymy zbiory oczekiwań z obu kubełków (przepisujemy MNIEJSZE do większego) jednocześnie patrząc, czy jakieś elementy się nie pokrywają - jeśli się pokrywają, to znaczy, że możemy wykonać daną reakcję - więc ją wykonujemy. I tak aż do końca.

Za to mam 9/10, w ostatniej grupie dostałem 2x błędy wykonania (prawdopodobnie przegiąłem z pamięcią - trzeba było jednak czyścić sety, które już były zużyte :P), ale czasowo to wyrabiało.

Mamy wszystkie łączenia w tablicy, odrzucamy na wstępie te reakcje które nie zajdą nigdy, co do pozostałych wiemy że zajdą gdzieś w przedziale od pierwszego do ostatniego łączenia, ale nie wiemy gdzie. Piszemy funkcję która robi binsearch - łączymy do połowy przedziału badanego i dzielimy na reakcje które zajdą w pierwszej połowie i w drugiej. Łączenia w Find&Union bez kompresji ścieżek więc możemy je cofać bez problemu i wywoływać funkcję gdy stan FAU jest odpowiedni :) Gdy już wiemy kiedy substancje każdej z reakcji się spotkały, to jest prosto.

10/10 algorytm LCA

Buduje drzewa na ktorym dla kazdej reakcji szukam wspolnego przodka oraz przelewki jej poprzedzajacej. Nastepnie sortuje reakcje po znalezionych przelewkach i przeprowadzam tak jakby wszystko bylo od poczatku w 1 probowce.

Trzeba tylko uwazac na podpuchy takie jak brak wspolnych przodkow (pomijamy reakcje) albo priorytety reakcji(stable sort).

Inne rozwiązanie:
1. Budujemy drzewo, w którym liśćmi są początkowe probówki a węzły wewnętrzne odpowiadają kolejnym operacjom przelania. Na drzewie budujemy strukturę do LCA.
2. Przeglądamy listę reakcji i dla każdej z nich za pomocą zapytania o najniższego wspólnego przodka w drzewie wyznaczamy chwilę czasu, w której dana reakcja zajdzie.
3. Sortujemy reakcje po czasach i symulujemy cały proces.

- w każdej fiolce trzymamy listę substancji
- listy łączymy przy przelewaniu fiolek (nie musimy używać zbiorów rozłącznych, bo zawsze używamy reprezentantów, czyli niepuste fiolki)
- krawędzie pomiędzy elementami list mają wagi będące numerem kroku, w którym listy zostały połączone
- dla każdej listy tworzymy drzewo przedziałowe (podstawowa struktura danych na pa) w oparciu o wagi
- dla każdej pary reagujących substancji możemy w lgn wyznaczyć w którym kroku nastąpiła reakcja (czyli max z wag między elementami na liście)
- sortujemy listę krawędzi (krok reakcji, priorytet reakcji)
- symulujemy wszystkie reakcje

Piotr - nie trzeba tworzyć węzłów odpowiadających połączeniom, w zupełności wystarczą wierzchołki odpowiadające fiolkom.

Buduję drzewo (las właściwie) kolejnych fiolek. Liśćmi są fiolki startowe, kolejnymi węzłami produkty zmieszania (czyli jak mam 10 fiolek i zlewam 2 do 9, to produkt nazywam jedenastą, tylko pamiętam, by gdy przyjdzie polecenie zlania 9, to tak naprawdę mam zlać 11).
Co najmniej jedna fiolka nie ma rodzica. Takie fiolki mają głębokość zero, przechodząc drzewo wyliczam głębokość pozostałym.
Każdy wierzchołek poza indeksem rodzica ma zestaw przodków, 1,2,4,8....
Dzięki temu w czasie log^2(n+m) jestem w stanie odpowiedzieć na pytanie, w którym ruchu zlana została substancja a z b (znajdując najniższego wspólnego przodka). Skoro wiem w którym ruchu, to znam kolejność wykonywania reakcji (posortowane po parze <ruch, priorytet>) to wykonuję je po kolei.
Łącznie log^2(m+n)*k.
Zadowolony z siebie zająłem się innymi zadankami, a tu... 4/10, bo zaćmienie mnie ogarnęło i co prawda zabezpieczyłem się przed wysokimi drzewami we właściwej części algorytmu, ale przodków rzędu 1,2,4,8... wyliczałem kwadratowo ( a wystarczy przejść drzewo w głąb trzymając jednocześnie na "stosie" z losowym dostępem drogę korzeń-odwiedzany wierzchołek, byłoby nlog[n])

Chyba jedyne w historii zadanie z ostatniej rundy, które zmaksowałem, więc się pochwalę ;).
Z kroków mieszania zrobiłem las w taki sposób, że zmieszane fiolki wkładałem pod jednego rodzica. Ponumerowałem poziomy w drzewach od dołu, a potem po znalezieniu najniższego wspólnego przodka dla dwóch substancji (czyli dla możliwych reakcji) wiedziałem, w którym kroku mogę wykonać mieszanie - w takim, jaki jest numer poziomu w drzewie.
Przestraszyłem się tego pół miliona trochę i szukanie najniższego wspólnego przodka zrobiłem offline'owym algorytmem Tarjana, ale - patrząc na czasy i limity - logarytmiczne szukanie też by raczej przeszło. Co ciekawe, udało mi się ułożyć taki test, na którym rekurencyjna wersja kończyła się segfaultem na zagłębieniu stosu, więc przerobiłem na iteracyjną. Obie dostały po 10 punktów :).

Aha, no a jak kolejność reakcji już jest przypisana, to to liniowo posortować i wykonać.

Mam tak jak Piotr i Grzegorz. Wyznaczanie LCA zmodyfikowanym algorytmem Tarjana. Max czas 1.31s

W założeniach było napisanie algorytmu takiego jaki opisał Kamil. Ale czasy pokazują, że wyszło mi coś zupełnie innego... będę musiał to przeanalizować.
Z tych ciekawszych rzeczy, też miałem problemy z pamięcią. Moje rozwiązanie przekraczało 250MB dla największych testów. O dziwo okazało się, iż winowajcą była kolejka std::queue, która zjada niewyobrażalne ilości pamięci. Naklepanie najbardziej prymitywnej kolejki na vectorze, zmniejszyło zapotrzebowanie do 50MB... i pozwoliło cieszyć się jednym TLE na grupę. :/
Wynika z tego, że nie opłaca się używać STLowej kolejki jak ma się problemy z pamięcią.

Mi wyszło:
O( N * log(M) + (M + K) * log(M) * log_star(M) + K * log(K) )
skoro M < N to mamy również:
O( (N + K) * log(N) * log_star(N) + K * log(K) )
i pamiętamy że log_star(reality) < 5.

W czasie M * log_star(M) można zapuścić symulację M przelewań z Find'N'Union celem ustalenia (w dowolnym momencie w trakcie przelewania) ktore pary fiołek są już zlane.

W czasie takiej symulacji wykonuje (maks 1 per reakcja) do K zapytań o to czy para substancji już jest zlana czy nie. To trwa K * log_star(M).

Te odpowiedzi dają nam możliwość zapuszczenia binsearcha po czasie {0..M} - czyli log(M) kroków potrzeba.

Więc robimy reset FnU w czasie O(N), i puszczamy powyższe [razem z resetem] log(M) razy.

Tym samym już wiemy dla każdej reakcji kiedy dwie fiołki w niej biorące udział się łączą.

Teraz wystarczy już przesortować reakcje w czasie K * log(K) [po czasie, dla równych czasów, to po numerze reakcji]. I zasymulować reakcje w czasie < nieskończoności [inf == m tutaj].

Ostatecznie chodziło do 1.5 sekundy na 10-tym teście.

U mnie tak jak u Kamila Wajdy.
Dodam, że moje pierwsze zgłoszenie z stlowym setem (ale ze zwalnieniem pamięci - wyszło mi, że w ten sposób moj program potrzebuje ok. 60 MB) weszło na 9 punktów z jednym TLE, więc miałem dobrą intuicję, żeby użyć własnej hash tablicy - przyśpieszyło ok. 3x, a i pamięć spadła do ok. 40 MB.

Dominik, poważnie ta kolejka tyle zzarla? Bo ja też jej używałem i tez mam przekroczenie pamięci na testach od chyba siódmego wzwyż. A wcześniej też po jednym tle na grupę. .. Czyli chyba mamy podobne rozwiązanie - liczyłem na 8-9 punktów, bo złożoność liniowo-logarytmiczna, ale przez te limity weszło na tylko trzy. Trudno, na przyszłość będę wiedział żeby nie używać standardowej kolejki itp. :)

Czy to było dużo małych kolejek? Jeśli tak, to potrafię wytłumaczyć problem: queue domyślnie używa deque, a deque alokuje miejsce na elementy po 512 bajtów na raz. Duża kolejka powinna zużywać pamięć w miarę optymalnie, ale mała nie.

Da się z tym jakoś walczyć? Podstawienie std::list do kolejki poprawie sytuacje tylko o czynnik 2. kolejka nie ma shrink_to_fit(), deque ma, ale jak się do niego dobrać?

Ja mogę dodać, że problem lasu i braku wspólnego przodka można było rozwiązać poprzez dodanie sztucznego korzenia, który był rodzicem wszystkich realnych korzeni. Dzięki temu nie było problemu z brakiem LCA czy niezachodzącymi reakcjami, gdyż wszystko co trafiło do sztucznego korzenia było ignorowane.

Tomek - nie, tylko jedna kolejka. Ale miałem też tablicę setów, których nie czyściłem po wykorzystaniu, więc niewykluczone, że to one uwaliły.

Tomek Czajka: Tak, oczywiście. Pamięć zabierało przygotowywanie miejsca na kolejne elementy, co w sytuacji, gdy będziemy trzymać wiele elementów nie jest wcale złe. Natomiast podczas pisania, w ogóle nie pamiętałem o tym "szczególe" implementacyjnym i tworzyłem n kolejek. Potem jak mi massif rzucił wykresem sięgającym 250MB to się trochę zdziwiłem. Nawet do poznania wyników cieszyłem się z tego, iż ogarniam valgrinda i poprawiłem 'pamięciożerność' mojego programu. Teraz tylko muszę dojść do tego, co sprawia, że mój algorytm działa jakby był kwadratowy... bo w założeniach był identyczny z rozwiązaniem Kamila.
Bartłomiej Szczygieł: Faktycznie kolejka na liście będzie zużywała sporo pamięci na wskaźniki, ale mimo wszystko będzie to znacznie, znacznie mniej, niż zabiera std::deque. Niestety nie można użyć forward list ponieważ std::queue wymaga dostępu zarówno do pierwszego, jak i ostatniego elementu. Można zatem napisać swoją własną kolejkę, która będzie posiadać tylko jeden wskaźnik na element, albo symulować kolejkę poprzez vector vectorów. W sumie to jest jedno z bardziej oszczędnych pamięciowo podejść.
Aczkolwiek w tym zadaniu wystarczyła klasa posiadająca vector ze wszystkimi elementami, które posiada oraz posiadała kolejka, oraz liczbę równą liczbie skasowanych elementów. To rozwiązanie ma taką zaletę, iż wymaga stosunkowo niewiele alokacji oraz jest w miarę szybkie, a wadę taką, że może przetrzymywać wiele zbędnych elementów. Zapewne gdyby mój algorytm wyglądał inaczej, zdecydowałbym się na na vector vectorów aby nie trzymać zbyt wiele zbędnych bajtów, albo nawet napisałbym własną implementację kolejki, w pamięci ciągłej, podobną do implementacji vectora, ale nie kopiującej skasowanych elementów... aczkolwiek teraz nie jestem pewien, czy zrozumiałem pytanie.

Hmmm... Nikt nie pisał algorytmu online do LCA? Zamiast głębokości węzłów zastosowałem numery kroków. Jedyną strukturą z STLa w moim rozwiązaniu był vector do list sąsiedztwa w drzewie fiolek.

Czas: O(n*log(n) + k*log(n) + k*log(k)) (najgorszy wynik: 0.78s)
Pamięć: O(n*log(n) + k) (spokojnie mieści się w limicie)

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

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.

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.

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.

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ą)