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.

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

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

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.

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.

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

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

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.

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.

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

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

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)

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.

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

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

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

@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

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

@Bartłomiej
Jeżeli podział przechodził przez prostokąt, to dopisywałem go do dwóch dzieci. Później jak ilość elementów się zmniejszała poprzez usunięcie kolidujących, to wracając także musiałem sprawdzać, czy prostokąt z liści nie jest tym samym. Oczywiście funkcja szukająca punktu podziału była taka, aby unikała dużej ilości przecięć z prostokątami.