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)

A ja choć częściowo wezmę w obronę limity w zadaniu PLE. Ze względu na to, że istnieje wiele ciekawych rozwiązań istotnie szybszych niż O(n^2) (tak jak O(n log n), O(n log^2 n), O(n^1.5) itp.), organizatorzy najwyraźniej postanowili, że wszystkie powinny przechodzić. To mogło być całkiem sensowne - dla wszystkich tych złożoności istnieją rozwiązania o mniejszych i większych stałych ukrytych w notacji O. Tak więc tutaj byłoby bardzo trudnym zadaniem oddzielenie wszystkich rozwiązań np. O(n log n) od wszystkich o złożoności O(n log^2 n). Mogłoby wtedy dojść do sytuacji, w której np. klepię n log^2 n -> nie wchodzi mi -> bawię się niskopoziomowymi optymalizacjami i robię fast input -> weszło.

To samo w sumie dotyczy limitu pamięciowego. Jeśli ktoś jest w stanie uzyskać złożoność pamięciową istotnie lepszą niż (1000000)^1.5 czy O(n log^2 n), to już niech ma te 10 punktów - w końcu to jest kategoria [B], limity mogą być nieco luźniejsze ;).

Ale prawdą jest, że jeśli już pozwalamy na takie luźniejsze limity czasowe, to musimy się postarać, by uwalić programy o złożoności O(n^2). Rozumiem oczywiście kwestie w stylu "jeśli damy 10 paczek po 10 testów i w każdym limit rzędu 15s, to będzie nam się sprawdzać pół dnia". Jednak wydaje mi się, że wszelkie usprawnienia O(n^2) powinny nie przechodzić niezależnie od kosztów... Zdziwiło mnie na przykład, że nie ma takiego testu, o którym mówił Wojtek - dużo wąskich i długich prostokątów (wierzę mu, że takiego testu nie ma :P). Nie dość, że spowodowałby TLE w wielu rozwiązaniach, to bardzo możliwe, że doprowadziłby do przekroczenia pamięci w części programów.


A ja jeszcze trochę powiem o rundzie rozproszonej. Zadania były raczej niegłupie i (w mojej opinii) wymagały pomysłowości. Oczywiście możemy zrozumieć pewną ostrożność organizatorów, którzy być może za pierwszym razem nie chcieli proponować jakichś kosmicznych zadań, żeby nagle się nie okazało, że np. trzecim najwyższym wynikiem dnia jest 4p. Jednak zastanawia mnie jedna kwestia: czy nie mieliście przypadkiem wrażenia, że zadanie z [B] (Kółko) jest trochę trudniejsze niż równoległe [A] (Sekretarka)? ;)
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

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.

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.

Co do zadań to jeszcze było zadanie PAK. Rozwiązanie wzorcowe dosyć standardowe, ale limit n=24 i fakt, że na uruchomieniu próbnym działało prawie 5s albo dostawało TLE powodował zamieszanie i wątpliwości. Sporo czasu spędziłem szukając szybszego rozwiązania (coś w stylu 3^(n/2)), a skończyłem (tak jak chyba spora liczba zawodników) robiąc różne niskopoziomowe optymalizacje, które były zupełnie niepotrzebne. Przez tę sytuację to zadanie też zaliczyłbym do niefajnych w tej edycji. Co do reszty zadań to zgadzam się z tym co napisał Wojtek.
Dorzucę też swój komentarz do limitów czasowych w ostatniej rundzie. Limit 16s przy n=100k, gdzie rozwiązanie wzorcowe działa w O(n log n) poniżej sekundy jest dosyć dziwny. Sporo osób implementowało n log^2 n i biorąc pod uwagę, że to była ostatnia runda myślałem, że te rozwiązania zostaną rozróżnione na punktach (chociaż do tego n powinno być raczej większe). W CIA z kolei limity bardzo ostre. Miałem rozwiązanie o złożoności O((k-1)^(k!/2) * k!) co dla k=4 daje całkiem sensowną liczbę operacji (swoją drogą mniejszą niż w zadaniu PAK) i udało mi się osiągnąć czas 4s na uruchomieniu próbnym, a tutaj limity 2-3s. Przecież najprostsze bruty i tak by działały zdecydowanie za wolno, więc czemu nie nagradzać rozwiązań, które są jakkolwiek lepsze ?
Teraz system SIO2: system jest sprawny, szybki i schludny, ale w kontekście potyczek brakowało mi zakładki "Moje wyniki", która by działała tak jak w poprzednim systemie, czyli pokazywała wyniki ostatniego zgłoszenia dla każdego zadania. Jeśli się dużo submitowało i korzystało z uruchomień próbnych to trzeba było później szukać swoich wyników. I jeszcze taka drobnostka: menu po lewej się zwija w zależności od wielkości okna przeglądarki w związku w tym dział Forum zawsze miałem pod "Więcej", a z Forum korzystałem zdecydowanie częściej niż z działu Pliki czy Testy. Więc jeśli link do forum mógłby być wyżej to by było super :)

No dobrze, jak ktoś ma zacząć coś tu pisać, to kto, jak nie ja :P?
Nowy harmonogram: Co do niego, to wydaje mi się, że zdał egzamin. W poprzednich dwóch edycjach 6ta runda szła ludziom istotnie gorzej niż wcześniejsze i dwukrotnie próg na TOP20 był około 10-15 pkt niższy niż to szacowałem po rankingu 5tej rundy, a teraz wydaje się, że problem zbyt dużej liczby zadań na krótki okres czasu zniknął.
Zadania rozproszone: Też wyszło bardzo fajnie. Po rundzie próbnej i szerzącym się błędom w stylu "brak long longów w wyliczaniu indeksów" wśród wielu osób oraz cięższym testowaniu wpisanym w naturę takich zadań, obawiałem się, że jej wyniki będą trochę randomowe i wprowadzą dziwaczne fluktuacje do rankingu, ale tak się nie stało. No i całkiem trafna wydaje mi się uwaga Smu z innego tematu, że dziwne jest, że dane wejściowe rosły mniej więcej tak, jak liczba kompów - sprawia to efekt, jakby wszystkie testy poza jednym były maxtestami.
Dobór zadań: Prawie każde z zadań z osobna wydało mi się ciekawe (wyłączam LUS, bo one się nie liczą i CIA, bo moim zdaniem rozwiązanie Tomka jest, co tu dużo mówić, niczym zapierającym dech w piersiach swoim pięknem, a jakieś dziwne LP też chyba nie są takie fajne - widać było, że jakaś megaprzypadkoza wchodzi w grę w tym zadaniu), lecz zestaw jako całość nie okazał się moim zdaniem bardzo dobry. Według mnie zabrakło zadań różnicujących górę. Było CIA, które było niedostępne dla śmiertelników, było DRU, które było trudne, ale też bardzo fajne - trochę rozrzuciło czołówkę, ale raczej nie za szeroko, a reszta to był raczej must, jeżeli się myślało o dobrym wyniku, z ewentualnym marginesem bezpieczeństwa, na jakieś drobne uszczknięcia punktów. Ja na przykład popełniłem głupiego buga w kol, straciłem 9 pkt i była to już strata nie do odrobienia. W poprzedniej edycji były takie zadania jak GENom, RAPer, KRYształ, DZIałka, MROwki i one moim zdaniem bardzo dobrze zróżnicowały czołówkę, w topce każde z tych zadań było zarówno rozwiązane jak i nierozwiązane przez sporą część.
Podsumowując w skrócie - CIA było za harde, DRU spoko, a reszta za łatwa.
Jakość opracowań: Poza jednym przypadkiem raczej robota bardzo dobrze wykonana, ale testy do PLE, to jakaś masakra. Proszę poczytać temat o rozwiązaniach PLE - jest tam więcej opisanych rozwiązań O(n^2), które dostały 10/10 niż tych działających sensownie, a testy je uwalające nie wymagają przebłysków geniuszu i są raczej naturalne w trakcie opracowywania, a nie tylko "po fakcie". Testy nie były paczkowane, a bez tego się moim zdaniem nie da dobrze rozłożyć punktów. Chyba nikt nie zaprzeczy, że nieobecność takiego testu jak 100.000 wąskich prostokątów świadczy o fatalnej jakości opracowania. Poza tym time limit 16sec i memory limit 1024MB - o so chodzi??

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.

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

@Tomek, wydaje mi się, że log^2 n, bo w dowolnym wierzchołku drzewa przedziałowego może się znaleźć więcej niż jeden prostokąt, chyba że przechowywałem je niepotrzebnie :)

@Ryszard: Jak w drzewie kd prosto sprawdzasz, czy nastąpiła kolizja gdy dodawany prostokąt nie zawiera żadnego punktu z drzewa? Bo albo dodawany jest mały, albo wysoki i przecina się z szerokim a płaskim

> czy jeden długi a wąski prostokąt nie zajmuje Ci
> przypadkiem Θ(n) węzłów w tym quad tree?

Zdaje się, że tak faktycznie jest :( Co prawda pojedynczy prostokąt u mnie zawsze zajmie tylko 1 węzeł (bo optymalizuję drzewo trzymając tylko najwyższe potrzebne węzły w hierarchii), to jednak gdyby zrobić taką szeroką "zebrę" (maksymalnie długie prostokąty; jeden zaraz pod drugim) liczba węzłów per prostokąt byłaby liniowa (co gorsza względem max współrzędnej, lol!). Cóż, w takim razie pozostaje mi przyznać, że testy nie były najlepiej dobrane ;)

Ja mam MUZ na secie par longlongów, wczytuję scanfem, i działa mi 0.56s.

Wojtek: W sumie nawet nie przepisywałem z mniejszego do większego zbioru, tylko też na pałę; to mógłbym poprawić.
Też mi się zdawało, że moje rozwiązanie powinno działać w jednym przebiegu, ale testy pokazały mi, że nie zawsze i też nie wiem czy to bug w kodzie czy błąd w idei. W przypadku Twojego rozwiązania jeszcze bardziej mi się wydaje, że to rzeczywiście powinno działać w pierwszym przebiegu (w przypadku mojego wydawało mi się, że dwukierunkowość krawędzi to załatwia).

@Adrian Ładnie! To chyba wychodzi złożoność O(n log n) a nie O(n log^2 n)?

Ja dostałem za to 10/10, miałem dobre czasy (20% limitu czasowego w przypadku większych testów) i zrobiłem to używając drzewa kd, a sam algorytm był banalny:
- sprawdzam, czy z jakimś koliduje, jeżeli tak, to usuwam z drzewa kolidujący i zwiększam obszar tego, który chcę dorzucić
- jeżeli z niczym nie koliduje, to wrzucam do drzewa.