Informatyka UJ forum

hansu

Kod tego zadania to pud i jest dostepne tylko w trybie TEST_FINDER.

przem

jak sie komuś chce to niech walnie tutaj jakiś tutorial typu krok po kroku bo mnie już krew zalewa z tym zadaniem, tylko bez avli plizzz

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

luu

@cct: w swoim opisie mowisz zeby wyrzucic powtorki y .
Nie wiem czy dobrze rozumiem ale przeciez ta wlasne wyrzucona moze brac udzial w budowie wiezy.

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

chlebek

Yoter

ok, no to lecimy... mam tylko nadzieję że opiszę to jakoś przyzwoicie i zrozumiale...

1. czytamy pudełka robimy trzy wersje każdego z typów pudełek(tzn. wszystkie możliwe wybory 2-elementów z 3 jako podstawki, uwaga - pierwsza krawedz podstawki ma być mniejsza od drugiej, lub na odwrót) i wrzucamy to do jakiejś tablicy - powiedzmy boxes[]
2. do innej tablicy (która potem będzie naszym drzewkiem przedziałowym) nazwijmy ją tree[], wrzucamy wartości drugich krawędzi podstawki (tych dłuższych),uwaga w tree[] mamy trzymac w każdym elemencie dwie wartości - krawedz podstawki i wysokosc wiezy którą da się postawić na tej podstawce (init na 0)
3. sortujemy boxes[] po pierwszej współrzędnej
4. sortujemy tree[] po krawedziach
5. wyrzucamy z tree[] powtarzające się krawędzie
6. tworzymy z tree[] drzewko - coś jak pełny kopiec, najlepiej zrobić to tak: znajdź najmniejszą taką potęgę 2 która jest większa od ilości krawędzi w tree[] (po wyrzuceniu powtarzających się krawędzi) i przepisz krawedzie poczynajac od indeksu rownego znalezionej potedze
7. okej teraz jak już mamy drzewko to może opiszę jak się na nim działa - jeśli zmieniamy wartosc jakiegoś liścia to po prostu przechodzimy po sciezce i uaktualniamy, oczywiście do pewnego momentu, dodam że w drzewku, w wierzchołkach nie będących liśćmi mają się znajdować maxy z potomków. jak szukamy max - sprawa będzie dość prosta w naszym przypadku bo zawsze szukamy maxa w przedziale od pierwszej krawędzi w drzewie (czyt. pierwszego liścia) do krawędzi którą chcemy uaktualnić, robimy to tak: bierzemy pierwszą krawędź i idziemy po jej ojcach tak długo dopóki poddrzewo o korzeniu w danym ojcu nie wychodzi poza przedział, bierzemy jego wartość i robimy to samo dla następnego wierzchołka z przedziału, którego już poddrzewo nie objęło, przy okazji uaktualniając naszego maxa, o ile zajdzie taka potrzeba... (całość zresztą chyba Lupus opisał wcześniej...)
8. ok mamy boxes[], mamy tree[], teraz potrzebujemy jeszcze jednej tablicy - bufora :) po co on nam to zaraz samo wyjdzie...
9. przygotowania zakończone - czas na właściwy algorytm: idziemy intem i po boxes[], wyszukujemy binsearchem drugą krawędź z boxes[i] w tree[] i teraz dwie możliwości: jeśli pierwsza krawedz z boxes[i] nie rózni się od wcześniejszych obsłużonych (tzn. boxes[i].pierwszakrawedz == boxes[i-1].pierwszakrawedz) to bierzemy maxa z przedzialu [pierwsza krawedz w tree[] (pierwszy liśc), indeks naszego elementu - 1] i jeśli (max + trzecia krawędz rozpatrywanego pudłka > aktualna wartosc pod znalezionym indeksem w tree[]) to wrzucamy do bufora indeks z tree[] który trzeba uaktualnić i wartość jaką trzeba go uaktualnić (czyli max + trzecia krawędz rozpatrywanego pudłka), druga mozliwość to boxes[i].pierwszakrawedz > boxes[i-1].pierwszakrawedz, tutaj zanim obliczymy max z przedziału robimy flush() na buforze, tzn. wszystkie elementy z bufora po kolei wpychamy do drzewa i uaktualniemy drzewko, potem już tak samo, szukamy maxa jeśli jest potrzeba to wsadzamy wynik do bufora itd.
10. po wykonaniu całej pętli robimy jeszcze raz flush() na buforze i zwracamy tree[1].wyskoscwiezy :D

i to by bylo chyba na tyle... mam nadzieję że się nigdzie nie rąbłem.... ja wiem że to jest cholernie niezrozumiale opisane, ale jeśli zaraz nie padnę to zarzucę jeszcze loga z przebiegu algorytmu dla przykladowego testu do zadania i sobie poczytacie, może zobaczycie jak to działa... jak coś będzie niejasne to pytać.

EDIT: ok przyklad jest [link widoczny dla zalogowanych]

trywialna

Kurcze juz nie wiem gdzie moge miec blad... na testerce mateo mam wszystko OK nawet dla duzych danych a athina mowi ANS:/ ma ktos moze jakis pomysl co moze byc zle, albo moglby ktos zerknac w moj kod? robie na drzewkach przedzialowych, bylabym wdzieczna za jakakolwiek pomoc bo juz nie mam sily do tego zadania :?

Yoter

pamietaj że wynik mieści się w long longu, long longa ma też zwracać funkcja getmax() z drzewa przedziałowego, wynik najlepiej wypisuj przez cout i sprawdź czy aby na pewno dobrze budujesz drzewko... jesli dalej coś bedzie nie tak, to możesz podesłać kod, byc może będę w stanie Ci pomóc...

trywialna

Dziekuje wszystkim za pomoc juz przeszlo:)

krzycho

Mam dwa pytanka do opisu:
I. Jeśli chodzi o punkt 9.

Yoter

1. dla i == 0 jakkolwiek w sumie (nawet jesli zrobimy flush() na buforze to i tak jest on pusty :))
2. zaprawdę przed pierwszym flushem maximum jest równe 0

Ethlinn

straszne zadanie... szczegolnie gdy windows zaczyna wariowac przy long longach a ja nie mam pojecia co sie dzieje... kiedy debuggujesz printfami i nagle okazuje sie, ze w zasadzie to nic sie nie liczy w twoim programie to szlag trafia... albo gdy wychodzi ze 3>0... w pewnym momencie poczulam sie jakbym byla po drugiej stronie lustra, wszystko bylo szydercze, monitor wykrzywiał się w paskudnym wrednym uśmiechu, stacja chichotała pod nosem... mozana mnie do wariatkowa zamknac :D. Na szczescie sa jeszcze informatycy, ktorzy siedza po nocach i pomagaja innym :). I chwala im za to.

chlebek

Czy ktos moglby zobaczyc czemu juz od wczoraj meczy mnie TLE :/, bo ja juz nie moge , a kolos z MD jutro

Gorfin

Mam ten sam problem. Ktorej wersji qsorta uzywacie?

krzycho

Tez wczoraj mialem TLE. Jesli quickSort to moze pomoc randomizacja.
U mnie tez był porblem z partitionem z Cormena, gdy lewy przedzial zaczynal sie od 0(tablice od 0..MAX_TAB-1) bo dla tablicach od 1... MAX_TAB wszystko smigalo. Znalazlem gdzies na wikipedi ladnego partitiona obslugujacego tablice zaczynajace sie od komorki 0, dodalem randomizacje i przeszlo.

kafex

Partition Lomuto z randomizacją ownz :P jeszcze mnie w tym semestrze nie zawiódł :P

Ethlinn

jak wczesniej korzystałam z cormenowskiego quicksorta tak przy tym zadaniu musiałam przerzucić się na quicksorta z wykładu dr Ślusarka

chlebek

Madras

Dlatego wolę heapsorta ;].

Gorfin

Po dzisiejszym dniu zapamietam jedna rzecz - jak nie wiesz, jak przyspieszyc swoj program zrandomizuj qsorta ;)

dzendras

A ja po dzisiejszym dniu/nocy zapamiętam jedną rzecz... nie - dwie rzeczy. Po pierwsze: 2^16 != 64536, tylko 65536.
Po drugie: gdy w quicku robię sortowanie względem wielu kluczy, to nie należy zapominać o wstawianiu w partitionie wielu else.

Okaaaay? Right!

Te dwie rzeczy kosztowały mnie ładnych pare godzin. A teraz idę spać.

r4ku

ja przez 3 dni walczylem z avlami. dzis biore sie za alternatywne metody bo juz cierpliwosc do avli mi sie wyczerpala :/

kg86

drzewka przedzialowe to na prawde fajna i przyjemna sprawa, jak pomysle ze mialbym zamiast tego przepisywac AVL'a to chyba bym ocipial :P a tak, cala implementacja tej struktury + jego obsluga zajela jedyne 50 linijek... :)