Informatyka UJ forum

Robson

Moze ja glupi jestem ale dla mnie rozwiazanie na AVLach wcale nie jest trywialne...

A jak nie lubi ktos avli, to jest masa innych podobnych struktur danych.

No a wracajac do limitow pamieciowych... teraz to mozna cos takiego zrobic:
Posortowac ciag wedlug drugich krawedzi i z posortowanego ciagu utworzyc cale drzewo zrównowazone, bez pisania avli, tylko pozaznaczac ktore wierzcholki sa nieuzywane... tylko ze pewnie nie wyrobi cos takiego pamieciowo.... :P

Wogole wydaje mi sie ze te avle szybciej by poszly w kursorowej reprezentacji (na wlasnej tablicy) (bo w rozwiazaniu na linkach moze byc duzy narzut zwiazany z dispose/new ), a i tak jestesmy ograniczeni przez n*3 insert/delete, wiec lepiej liniowo to do pamieci wstawiac... i tak sie zmiesci...

jagm

Rogal

Ehhhh, już nawet wiem jak to zrobić.

Jeśli nie ma lepszego rozwiązanie to jest to chyba najmniej udane zadanie w tym roku.

kg86

ja wykminilem algos o zlozonosci tak dokladniej ok: 6n * log(3n) + 15n :D i nie uzywam AVL'i tylko takiego specjalnie skonstruowanego drzewka :) w zasadzie tylko sortowanie dziala mi tak dlugo (sortuje po dlugosciach i szerokosciach), reszta idzie liniowo... i zastanawiam sie, czy ma to szanse zmiescic sie w czasie ;P ale na 99% algorytm jest poprawny :)

@rogal - a Ty jaka masz zlozonosc? :)

smas

Mateo gratulacje ;d

edited: hehe STL;d

kg86

smas

kg86

@Mateo - jaka miales zlozonosc tak dokladnie? :) liczac z petlami liniowymi ;)

Roxel

Uff.. wreszcie sie udalo :D
RBT rocks!

Hetman prosil o binarke.. and here it comes:
[link widoczny dla zalogowanych] (z printfem niestety long longi sie krzacza w windzie)
[link widoczny dla zalogowanych] (z coutem)
[link widoczny dla zalogowanych] (linuksowa)

Spectro

Drzewa w tym zadaniu to jednak przekleństwo :? . Ten sam algos z drzewami z STLa zamiast ręcznymi AVLami dostał OK. Cóż, trzeba powalczyć z ansem... :/

edit:
U mnie następnikiem mógł być największy element w prawym poddrzewie (i analogicznie dla poprzednika najmniejszy element) ;] . Ciekawe tylko, że takie coś wyszło dopiero przez przypadek dla testu wielkości 100 000 O_o .

Lupus

Ja znam rozwiązanie, do którego nie trzeba AVLa ani drzew czerwono-czarnych. Za to (pewnie w jakiś inny sposób, nie wiem za bardzo jak wygląda to rozwiązanie z AVLem) wykorzystuje drzewo przedziałowe, które na pewno łatwiej napisać i ma mniejszą stałą niż AVL.

Nie wiem czy dobrze to nazywam drzewem przedziałowym... ale zdaje mi się, że tak.

Idea jest taka, że mamy tablicę od 1 do n, w niej jakieś wartości. I teraz chcemy szybko sprawdzać jaki jest max z elementów w komórkach z przedziału od 'i' do 'j'. Uaktualniać jakieś elementy tej tablicy i znowu sprawdzać max z jakiegoś przedziału. Normalnie takie sprawdzanie trzeba by to robić liniowo, ale można w czasie lg(n) .

Całe to drzewo można zaimplementować w tablicy, tak jak kopiec. (parent jest w indeksie i/2, lewy syn to 2*i, prawy syn to 2*i+1).

Deklarujemy tablicę, która będzie pełnym drzewem binarnym. Ale takim całkiem pełnym, tzn. o rozmiarze 1, 3, 7, 15, 31 itd .'] Niech będzie że ma rozmiar 'n'. W liściach tego drzewa (w komórkach od (n+1)/2 do n) trzymamy wartości z których chcemy obliczać max. W każdym innym wierzchołku (od 1 do n/2) trzymamy aktualne maksimum (albo numer liścia w którym znajduje się to maksimum) ze wszystkich wartości w poddrzewie zaczepionym w tym wierzchołku.

Czyli np. jeśli potrzebujemy pamiętać 6 wartości, to musimy zadeklarować tablicę na 15 elementów (numeracja od 1 do 15), która będzie symbolizować pełne drzewo binarne o 15 wierzchołkach, z których 8 jest liścmi. Liście tego drzewa są w numerach od 8 do 15. W liściach właśnie trzymamy te 6 wartości, z których obliczać będziemy max (w komórkach tablicy od 8 do 14).

Teraz np, w wierzchołku 4 trzymamy max z wartości z komórek 8 i 9. W wierzchołku 2 trzymamy max z wartości 8, 9, 10 i 11. W wierzchołku 6 max z 12 i 13, a w wierzchołku 1 max z całego drzewa .']

Żeby odczytać jaki jest max z jakiegoś przedziału to trzeba sprawdzić co najwyżej lg(n) wierzchołków. Np. jak chcemy sprawdzić jaki jest max w liściach od 8 do 14, to trzeba sprawdzić co jest w 14, 6 i 2.

Po wpisaniu nowej wartości do jakiegoś liścia, trzeba uaktualnić niektóre wierzchołki na drodze od tego liścia do korzenia (znowu lg(n)).

Żeby napisać jak to dokładnie wykorzystać w tym zadaniu, musiałbym całe rozwiązanie napisać. Nie wiem czy mam to zrobić, czy wystarczy taki hint.

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Naprawdę ciekawa sprawa z tymi drzewami przedziałowymi - uprościłoby to trochę rozkminianie samemu.

Ogółem, to można zrobić to jeszcze nieco inaczej, nie wchodząc w drzewa przedziałowe - własna mapa działająca na binsearchu.

Idea

- Założenie (dla ustalenia uwagi, bez straty ogólności): w algorytmie głównym rozpatrujemy pudełka w kolejności malejących szerokości (x), za to rosnących głębokości (y) - dla odwrotnego założenia wstarczy odwrócić oczywiście nierówności wszędzie.

- Z każdym kluczem skojarzone są wartości: wartosc (w którym trzymamy maksymalną wysokość do tej pory uzyskaną dla tej głębokości pudełka) oraz max (w którym trzymamy maksymalną wartość prawego poddrzewa w drzewie wyszukiwań binarnych, czyli de facto największą wysokość do tej pory uzyskaną dla wszystkich większych głębokości y pudełka).

- Do mapy wrzucamy jako klucze wszystkie wartości y wczytane, sortujemy je, wyrzucamy powtórki.

- Wyszukiwanie binarne ma fajną tutaj właściwość - zawsze znajdujemy element, więc nigdy nam się nie zapętli ;)

- Teraz jak chcemy znaleźć maksymalną wysokość dla kluczy większych od Y, to zapuszczamy binSearcha ze zmienna np. maksimum = 0:

a) jeśli siedzimy na elemencie szukanym, to porównujemy maksimum z polem "max" dla klucza na którym siedzimy, i ew. poprawiamy jego oszacowanie

b) jeśli szukamy czegoś większego niż element na którym siedzimy, to po prostu szukamy dalej

c) jeśli szukamy czegoś większego niż element na którym siedzimy, to porównujemy maksimum zarówno z polem "wartosc", jak i "max" skojarzonymi z elementem na ktorym sie znajdujemy - i oczywiście poprawiamy oszacowanie maksimum, jeśli któryś z nich jest większy.

Innymi słowy punkt c - jeśli skręcamy na ścieżce wyszukiwania w lewo, to musimy zapamiętać maksimum z prawego poddrzewa, bo w nim znajdują się ygreki większe od szukanego (a jego wartość znajduje się w polu "max" węzła na którym skręcamy) oraz wartość "wartosc" węzła na którym skręcamy - bo też jest większy od naszego docelowego. Punkt a i b myślę nie wymagają komentarza.

EDIT o uaktualnianiu ścieżek:
Jednak przechodzi spokojnie ścieżka ze zwykłym uaktualnieniem ścieżek po ich przetworzeniu. Robi się to prosto:

- gdy siedzimy na elemencie, którego oszacowanie uaktualnialiśmy, to zapamiętujemy wartość jego pola "wartosc" w jakiejs zmiennej, np. temp

- gdy wychodzimy z rekurencji BinSearcha (bo musimy go realizować rekurencyjnie, właśnie po to, aby na stosie rekurencji była zapamiętana ścieżka do elementu!) w miejscu, w którym szliśmy w prawo (tj. element w węźle był mniejszy niż szukany), to sprawdzamy, czy nasz temp nie jest większy niż pole max tego rekordu; jeśli tak - to je uaktualniamy

(Przeszła mi ta wersja też przez Athinę).

Ogółem, złożoność tworzenia drzewa to sortowanie, a wyszukiwanie maxa to Th( lg( ilośćRóżnychKluczyY ) ) - a ściślej mówiąc, dwukrotny przegląd każdej ścieżki (liczenie wartości dla danego klucza, a później ew. propagowanie jego wartości w górę).

Jakby coś było niejasnego to mogę postarać się szerzej wytłumaczyć, teraz muszę na zajęcia uciekać.

EDITED@Prezio: mówisz - masz:

Powyżej znajduje się rysunek ilustrujący działanie podpunktu c. To jest mapa dla testowego zestawu danych. Strzałeczki pokazują jak szukamy szóstki:

1. najpierw trafiamy na piątke (1 + 7)/2 = 4, a w pozycji 4tej w tablicy jest element o kluczu 5), ale ponieważ jest mniejszy, to nas nie interesuje

2. Idziemy w prawo = czyli na pozycję ( 5 + 7 )/2 = 6; na pozycji 6 w tabeli znajduje się element o kluczu 7; ponieważ klucz 7 jest większy od naszej szóstki, to wiemy, że wszystkie elementu w jego prawym poddrzewie są też większe - więc bierzemy z nich maxa, którego mamy zapisanego w rekordzie elementu na którym siedzimy; także ta siódemka jest większa od naszego elementu, więc bierzemy też wartość skojarzoną z tym kluczem;

3. Idziemy w lewo = na pozycję ( 5 + 6 )/2 = 5; na pozycji piątej w tabeli znajduje się nasza szóstka, więc teraz wiemy, że jedyne pozostałe elementy większe od niej, których nie rozpatrzyliśmy wyżej, to te znajdujące się w jej prawym poddrzewie. (Akurat w tym przykładzie takich nie ma). No to jak już mamy policzone maksimum wszystkich elementów, które są większe od naszej szóstki, to sprawdzamy, czy to maksimum + wysokość elementu, który rozpatrujemy w algorytmie, jest większa od dotychczasowej wartości dla szóstki - jeśli tak, to zwiększamy.

Mam nadzieję, że trochę pomogło.

Jeśli chodzi o samą mapę, to oczywiście wystarczy trzymać zwykłe rekordy z kluczami:

Prezioso

Dzięki. Ale jakbyś jeszcze zaprezentował to na prostym, małym przykładzie to byłbym wdzięczny :) :D

Spectro

Teraz, cct, napisz ile to rozwiązanie ma linii :mrgreen: . Moje rozwiązanie z AVLami ma ok. 300, biorąc drzewa z STLa wychodzi 80, a dodatkowo z qsortem z STLa wyjdzie jakieś 60 :P .

Heh, u mnie założenie jest takie, że drzewo jest niby sortowane po drugiej współrzędnej, a tak naprawdę po wartościach aktualnie najwyższej wieży o podstawie w danym wierzchołku. Po wstawieniu elementu do drzewa ustawiana jest ta wartość na sumę wysokości wieży poprzednika i wysokości właśnie dodanego klocka. Po czym usuwane są wszystkie następniki wstawianego węzła, które mają wartość wieży niższą lub równą, po czym można przejść do następnego elementu w posortowanej tablicy i zająć się nim w podobny sposób. Wynikiem ostatecznym jest oczywiście element maksymalny w drzewie ;) .

Taki jest szkic mojego rozwiązania, na wszystkie uściślenia i szczególne przypadki postępowania proponuję wpaść samemu :P . Tak czy siak, rozwiązanie jest bardzo proste, ale wymaga zaklepania drzewa zrównoważonego ;] .

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Spectro

Lupus

cct - Twoja mapa realizuje właśnie dokładnie to co drzewo przedziałowe.

Hetman

nareszcier :D
4233 P Tue, 28 Nov 2006 18:26:30 CET OK

ale juz nie chce miec wicej takich problemow ze zrobieniem w sumie nie tak strasznie trudnego zadania...

nie chce mi sie pisac o bledach jakie mialem....za duzo ich bylo

Roxel

@Hetman: najpierw Ci binarki daje, a potem mnie w rankingu wyprzedzasz :P

Spectro

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

@Lupus - realizuje co innego (drzewo przedziałowe jest jednak dużo praktyczniejsze), oraz w nieco inny sposób (inna organizacja pamięci). Ale jakieś podobieństwo jest.

@Spectro - faktycznie, brzmi przekonująco (a propos braku 'liniowienia się'). Co nie zmienia faktu, że jednak nie binSeach w wersji tablicowej - a nie drzewowej - łatwiejszy, przyjemniejszy etc. ;)))

Yoter

P to ZLOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO... :O

swiecmich

owszem, i zapowiada sie zarwana nocka na tym :/ i pozniej prosto na analize :/

hansu

Ufff, poszlo. 788 linijek, z pelnymi, pieknymi AVLami :] Na virgo jest testerka do tego zadania, tylko wejscia musza byc w takim formacie jak na SPOJu (czyli bez liczby zestawow na poczatku i program konczy dzialanie po wczytaniu liczby pudelek rownej zero). Wiem, ze juz niewiele czasu zostalo, ale jesli ktos bedzie zainteresowany wersja z AVLami to niech da znac tu na forum, to walne jakis tutorial... Tradycyjne dzieki dla matea za testerke i odpowiedzi na upierdliwe pytania...

Yoter

więc wyszło Ci 788 w końcu? :D ja mam około 400 (bez komentarzy i zbędnych pierdół pewnie duuuużo mniej) na drzewach przedziałowych... jakby ktos chciał to ja też mogę walnąć tutorial ale dla drzewek przedziałowych... fajna strukturka danych... ale i tak pewnie bym siedział jeszcze dłużej nad tym zadaniem (albo w ogóle go nie przepchnął) gdyby nie Robson... :D

ps. próbowałem przetestować P na virgo parę godzin temu i nie było jeszcze testów chyba... mateo to jakoś ostatnio chyba wrzucił?