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ć.

No jak robiliście to zadanie koksy?
Ja napisałem w sumie 5 różnych rozwiązań, z czego wszystkie były blefami, ale jeden przechodził wszystkie testy z forum (noo, spośród tych 50k Marka to tylko z 10k przetestowałem :P) i finalnie dostał 8/10 pkt, a te 2 pkt ucięte za WA. Z czego o tym, co wysłałem to nie wiem, czemu nie działa, a o innych wiem :P.
EDIT: Ups, właśnie zauważyłem, że już był temat o rozwiązaniu PLE, sorka za dublowanie :P.

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

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

Ciekawe pomysły. Przemyślimy pod kątem następnych zawodów.

- 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

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.

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

oj nie...

Podzieli się ktoś komu weszł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.

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.

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

Podpisuję się pod prośbą;)

brak newline'a at end-of-file pewnie