Ja w muz miałem rekurencyjne drzewo przedziałowe. To ile razy je pisałem można policzyć na palcach jednej ręki (jednak ta liczba zwiększyła się dzień wcześniej w trakcie pisania nawet dwuwymiarowego drzewa rekurencyjnego w PLE, które i tak okazało się blefem :P). Rekurencyjne przedziałówki są wolniejsze, ale niektórych zadań się na iteracyjnych nie da zrobić albo jest to dużo mniej wygodne (takich ala bit aktualności mówiący "wszystko pode mną jest bez sensu"), a to był ten przypadek dla mnie.
Moje drzewko musiało wspierać operacje
1) Dodaj x na przedziale
2) Maksuj z x na przedziale
3) Czytaj w punkcie
A co do kol, to uwaga Marcina wydaje się całkiem trafna.

Ja nie miałem, żadnego seta w muz, przeskalowywałem sortem i oprócz tego miałem tylko jedno drzewo przedziałowe. Jestem jednak świadom, że mogłem trochę stałą zbić.

Za to seta użyłem w drużynach i oddałem tym samy 2 punkty :(

A co do limitów czasowych to w cia powinny być według mnie bardziej zróżnicowane w obrębie jednego k, żeby rozróżnić rozwiązania, które to robią trochę za wolno od rozwiązań, które tego wcale nie są w stanie przeliczyć. (Trochę smutne, że moje rozwiązanie które działa niewiele dłużej niż te 3 sekundy dostaje 6 punktów).

I ocenianie w kol, też mi się trochę nie podobało. Powinno być tak że jest zawsze 100 kompów tylko dane rosną. A tak jak teraz to wygląda jakby każdy z testów był prawie max testem i jakby rozwiązanie 4-5 razy za wolne miało dostać 1/10.

Pewnie używacie STL-owego set'a - ja go unikałem, bo on wolny, alokuje i zwalnia pamięć przy każdej operacji. Może jakby w nim podmienić allocator na jakiś lepszy to by szybciej działał.

Adrian, nie potrafię zrozumieć Twojego rozwiązania. W każdym razie też mam O(n log^2 n), i liniowa pamięć.

Przechodzę prostokąty rosnąco po y2, i trzymam zbiór poziomych odcinków, ich górnych brzegów. Za każdym razem muszę znaleźć w tym zbiorze jakiś odcinek, który przecina nowy prostokąt. Prostokąt mogę tu potraktować jako nieograniczony z góry, co ułatwia sprawę. Jak znajdę przecięcie, to łączę prostokąty i usuwam odcinek ze zbioru.

Odcinek przecina prostokąt na dwa sposoby:
(a) jego lewy wierzchołek znajduje się wewnątrz prostokąta, albo
(b) przecina on pionową półprostą (lewy brzeg naszego prostokąta)

W tym celu mam dwie struktury danych:

(a) Zbiór lewych końców odcinków. Potrzebuję szukać punktów w prostokącie x1 <= x <= x2, y1 <= y. W tym celu mam strukturę danych Priority Search Tree - drzewo binarne, które trzyma najwyższy punkt w korzeniu, a pozostałe są podzielone pionową prostą przez środek.

(b) Zbiór poziomych odcinków. Potrzebuję szukać odcinka przecinającego pionową półprostą. W tym celu mam dwu-wymiarowe Interval Tree, czyli drzewo binarne, które w korzeniu trzyma zbiór odcinków przecinających prostą przez środek, a w poddrzewach odcinki na lewo i na prawo od tej prostej. Zbiór odcinków w korzeniu trzymamy jako dwa zbiory punktów (lewe i prawe końce), każdy z nich to taki sam Priority Search Tree jak w punkcie (a).

A ja naiwnie doszedłem do wniosku, iż rozwiązania takiego jak Pawła (również na posortowanym ciągu) nie opłaca się pisać i lepiej poddać zadanie niż poświęcić czas na wątpliwy punkt, czy dwa...
Teraz będę sobie to wypominał do następnej edycji potyczek...

On Sun, May 18, 2014 at 10:30:37PM +0200, Wojciech Sidor wrote:
> A ja się zapytam co to jest za magia:
[...]
> Wie ktoś co tu się stało?

1) out of disk space or inodes or hardware error

df tmp;df -l tmp; dmesg -T |tail -20

2) $ wc tmp
wc: tmp: Jest katalogiem
0 0 0 tmp

;)

Jeju, co za fuszera w testach, skoro rozwiązanie Pawła przeszło xdd. Przecież ubija (tzn. wymusza O(n^2) operacji) je test tworzony wzorem, który wrzuciłem w poprzednim temacie ;/. Swoją drogą też dziwne, że nie było paczkowania, do zadania była masa heur. Niby można wiele patternów pakować do jednego testu, ale wtedy poszczególne ich kawałki będą małe i mogą nie ubić na czasie. I to, że ja dostałem 8/10 pkt z czego 2 WA, to też najlepiej o testach nie świadczy.

W muzeum moim zdaniem wcale nie było wysokiego limitu. Ja miałem 2.63/3.00, a Smu 2.01/3.00, a obaj mieliśmy wzorcową złożoność i ja bym się bardzo zdziwił, jakby nie weszło. Choć w ple rzeczywiście jakieś strasznie wielkie.

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

Mój program przechodził po kolejnych początkowych wierzchołkach prostokątów (jakaś lista/kolejka). Na początku była ona wypełniona posortowanymi niemalejąco punktami x1, sprawdzał czy są takie obszary, których x1 jest co najwyżej taki jak jego, a x2 jest większy od x1 aktualnie analizowanego. Wartość x1 tego złączonego obszaru dodawał na początek tej listy. I zaczynał od nowa dla aktualnie pierwszego elementu tej listy/kolejki.
Samo wyszukiwanie obszarów, o x2 większym od x1 obecnego i zarazem x1 nie większym, przeprowadzałem na drzewie przedziałowym.
W skrócie tak. Złożoność O(n*log^2(n)). Dostałem 10/10.

Nie dziwię się że optymalizowałeś, po tylu maksach z rzędu presja aby nie uronić ani punkta na TLE musi być zabójcza ;)

n^{3/2}log n weszło na 10pkt. nawet nie zbliżając się do limitów czasowych. Trzymałem mapy dla każdej współrzędnej y oraz dla bloków [k*1000, (k+1)*1000) - w ten sposób zapytanie o rogi znajdujące się w danym prostokącie robiłem w sqrt(n)logn. Raz znaleziony róg usuwałem z mapy, żeby się ładnie amortyzowało. Problemem były takie przecięcia obszarów, że róg żadnego nie zawierał się w drugim, ale to można było załatwić na początku jednym przejściem miotłą.

moje rozwiązanie O(n^2):
-posortuj prostokąty po rzutach na oś X,
-w liście trzymamy nieprzecinające się prostokąty,
-dla każdego prostokąta, tak długo jak na liście jest prostokąt, z którym można się połączyć, łączymy, usuwamy stary z listy

dostało 10/10, bez sortowania na początku 3/10

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

Zwykle w Potyczkach bywają strasznie małe limity czasu, a w tej rundzie były olbrzymie, w porównaniu! A ja tak optymalizowałem mój kod :)

Moje najgorsze czasy:
cia 0.07s/3.00s
muz 0.41s/3.00s
ple 0.33s/16.00s
fio 0.64s/6.00s