Juliusz: Mi się wydaje, że ja robiłem dość podobnie, ale nie wyznaczałem pierwszego najbliższego prostokąta z każdej z 4 stron, a wszystkie widoczne (takich krawędzi jest <=3n-6 w jedną stronę, bo można z tego zrobić graf planarny) i dalej robiłem chyba coś podobnego, tzn. F&U z przepisywaniem krawędzi (rozumiem, że przepisujemy na pałę, ale z mniejszego do większego zbioru, tak?) ale zawsze robiłem tylko 1 przebieg, bo moim zdaniem rozważając wszystkie widoczne z danej strony, to jest ok, ale dostałem 8/10 pkt - 2WA. Nie wiem, czy to bug w kodzie, czy błąd w idei, ale jakoś nie działa, mimo że przeszło ogromną część testów z forum (tzn. nie na wszystkich Marka testowałem :P)

@Tomek, przechodzę po kolejnych prostokątach posortowanych według niemalejącego parametru x1. Dla każdego kolejno analizowanego prostokąta sprawdzam, czy wcześniej nie analizowałem takiego, który pod względem y1-y2 ma część wspólną z aktualnie analizowanym oraz jego koniec x2 jest większy niż początek x1 aktualnie analizowanego. Jeżeli tak, to możemy te prostokąty scalić. Aktualizujemy parametry x1,x2,y1,y2 dla tego złączonego prostokąta i dalej próbuję wyszukiwać kolejne prostokąty, które się z tym scalonym prostokątem przecinają. Jeżeli taki prostokąt już nie istnieje, to przechodzę do kolejnego prostokąta (pod względem x1) i powtarzam czynności.

Znajdowanie prostokątów mających część wspólną wykonałem na drzewie przedziałowym wielkości max{y2}. Z jego pomocą mogę znajdować te prostokąty, których x1 jest nie większy od aktualnie analizowanego (ze względu na kolejność dodawania) oraz mają część wspólną z (y1-y2) (ze względu na przedział na jaki dodaję dany prostokąt). Zatem jest to drzewo przedziałowe zanalizowanych już prostokątów, z którego pobieram prostokąt o maksymalnym x2 w przedziale (y1-y2).

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.

Warto jeszcze zauważyć, że dla k <= 3 odpowiedź to ceil((maksymalna odległość między dwoma ciągami)/2).

Dla k=2 startujemy z dowolnego ciągu i idziemy "w kierunku drugiego" (tzn. wykonujemy zmiany wartości w kolumnach, które nas oddalą o X od pierwszego, a przybliżą o X do drugiego). Oczywiście potrafimy oddalić się o tyle, ile chcemy. Mamy już jeden punkt.

Dla k=3 startujemy z ciągu najbardziej odległego od pozostałych i, podobnie jak poprzednio, idziemy "w kierunku" obu pozostałych (zmieniamy wartość w kolumnie o X, by oddalić się o X od tego najbardziej odległego, a przybliżyć o X do pozostałych). Nietrudno wykazać, że tak się da zrobić. No to mamy już trzy punkty. ;)

No, tylko że dla większych 'k' odpowiedź ta już nie musi być poprawna. :P

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

Zacznijmy od ustawienia wszystkich liczb na medianę z 5 wartości w danej kolumnie. Liczymy odległości. Teraz zmiana wartości w danej kolumnie o 1 odpowiada zmniejszeniu dwóch z tych odległości i zwiększeniu pozostałych trzech, albo ewentualnie zmniejszeniu jednej i zwiększeniu pozostałych czterech.

No więc zadanie sprowadza się do tego: mamy 5 liczb (odległości), i dla każdej pary z nich możemy pewną liczbę razy wykonać operację zmniejszenia ich, i zwiększenia 3 pozostałych. Drugą możliwość (zmniejszenie jednej i zwiększenie pozostałych czterech) można dla ułatwienia reprezentować dodając 6-tą liczbę -∞.

Tak więc zadanie sprowadza się do zadania na grafie nieskierowanym o 6-ciu wierzchołkach z wagami na krawędziach, ale o dziwo to nie koniec. Tu dopiero zaczyna się zabawa...

Można zauważyć, że nigdy nie warto użyć dwóch krawędzi nie mających wspólnego wierzchołka. To pozostawia nam tylko dwa rodzaje podgrafów: gwiazdę (tylko krawędzie z jednego wierzchołka), i trójkąt.

Ale to dalej nietrywialne. Ja ostatecznie zrobiłem to zachłannie: jeśli chcemy pomniejszyć maksymalną odległość, to trzeba użyć jakiejś krawędzi z wierzchołka o największej odległości. Można też udowodnić, że najlepiej wybrać krawędź do wierzchołka o jak największej odległości po drugiej stronie.

Tak więc już wiemy, którą krawędź najlepiej użyć w każdym kroku, pozostaje to zrobić efektywnie, bo tych krawędzi jest dużo (wagi można potraktować jako wielokrotne krawędzie). Trzeba grupować te kroki w grupy symulowane na raz.

Mój kod ma kilka różnych przypadków, zależnie od tego jak układają się te odległości oraz które krawędzie są jeszcze dostępne. Każdy przypadek przekształca się w inny po użyciu odpowiednią liczbę razy cyklu krawędzi występującego w danym przypadku. Cała symulacja działa w czasie stałym.

Chyba można to zrobić prościej, bez rozważania przypadków. Wystarczy iść po jednym kroku i wykrywać automatycznie cykl w symulacji. A następnie sprawdzać, ile razy ten sam cykl się jeszcze powtórzy.

Przypadki k<5 sprowadzałem do k=5 (duplikując dane ciągi), bo ten jest najprostszy ;)

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

Doszedłem do tego, żeby sprowadzić problem do ciągów o długości maksymalnie K! zamiast N, czyli 120x5 zamiast 100000x5, poprzez skonstruowanie ciągów B w których i-ty element jest sumą tych elementów ciągów A, na których elementy te są w porządku i-tej permutacji.
Wtedy jeżeli znajdę rozwiązanie w B, to mogę je przekształcić w rozwiązanie w A o takiej samej maksymalnej odległości - jeżeli na pozycji i-tej w ciągach B rozwiązanie jest pomiędzy ciągami x i y (x = perm[i][k], y = perm[i][k+1]) i powiedzmy Bsol[i] = B[i][x] + R[i], to w ciągach A rozwiązanie dla elementów z tej "permutacji" też przypadnie pomiędzy ciągami x i y i można je przydzielić dowolnie tak, żeby łącznie "zużyć" R[permclass[j]] na różnicę pomiędzy A[j][x] a Asol[j] (czyli Asol[j] = min(A[j][x] + R[permclass[j]], A[j][y]); R[i] -= (Asol[j] - A[j][x]).

Mimo takiego zmniejszenia rozmiaru problemu nie wymyśliłem co dalej i tego co miałem starczyło na 2 punkty :/.

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.

Ja na początku dla każdego prostokąta wyznaczam "bliski" prostokąt w prawo, lewo, górę, dół, zamiatając cztery razy w czterech kierunkach.
Tzn. np. najbliższy prostokąt w prawo to pierwsza napotkana przecinająca zakres y-ków lewa krawędź na prawo od jego własnej lewej krawędzi. Krawędzie wstawiam symetrycznie, czyli jak dla prostokąta i wstawię prostokąt j do prawych sąsiadów, do do prostokąta j wstawię od razu i do lewych.
Dostaję w ten sposób graf o 4*N dwukierunkowych krawędziach.

Następnie zachłannie merguje sąsiednie wierzchołki w tym grafie.
Dla danego rozważanego prostokąta wstawiam jego cztery zbiory krawędzi na cztery analogiczne do jego zbioru krawędzi set-y - prawo, lewo, gora, dol, każdy posortowany w odpowiednim kierunkach.
Teraz sprawdzam najmniejsze elementy wszystkich setów. Jeżeli z którymś się przecina, to łączę tamten prostokąt z obecnie rozważanym
- dodaje jego krawędzie prawe, do rozważanych prawych, lewe do lewych etc.
- ustawiam jego "parenta" w Find&Union na prostokąt do którego domergowałem, żeby przyszłe odniesienia do niego trafiały od razu do parenta.

Wydawało mi się, że to powinno zadziałać w jednym przebiegu (tzn. startując taką procedurę raz dla każdego prostokąta), ale albo miałem jakiegoś buga (a znalazłem parę po drodzę), albo jednak to tak nie działa, więc na koniec dodałem jeszcze pętlę bezpieczeństwa, która powtarzała wszystko od zera (łącznie z przeliczaniem na nowo początkowych krawędzi) aż w całym przebiegu nic nie połączyła. Ostatecznie (po ubiciu dodatkowo paru bugów) na testach z forów w łącznie kilkunastu na 200 testów potrzebowała więcej niż 2 przebiegi (czyli 1 niepusty) - maksymalnie 4 (3 niepuste).
Max czas na oficjalnych testach - 1.94s/12.

Ja użyłem quadtree. Czas i (niestety) pamięć O(nlogn).

Dla każdego kolejnego prostokąta sprawdzam najpierw czy przeciąłby się z jakimś dotychczas wrzuconym. Jeśli tak, to usuwam tamten i powiększam mój prostokąt - i tak aż do wyczerpania kolizji. Na koniec wrzucam mój (być może powiększony) prostokąt.

Pojedynczy prostokąt w quadtree może niestety wymagac O(logn) węzłów, stąd i całkowita pamięć O(nlogn).

Dostałem 9/10, na jednym teście się nie zmieścił czasowo.

Tak get[U]Int() bazowany o buf[64K] + syscall read() + własny getChar()/ungetChar() rządzi, nie mam pojęcia czemu i stdio i iostream są tak cholernie wolne.

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.

Podoba mi się ta metoda ze zgadywaniem - a ja naiwnie myślałem, że się z tym nic nie da zrobić...

Ja w muz wykorzystuję to, że ciąg jest rosnący i trzymam tylko miejsca w których on rośnie. Drzewko wspiera mi operację znajdowania następnego takiego miejsca. Moje niskie czasy wynikają też po części z własnej szybszej implementacji wczytywania liczb z wejścia.