Informatyka UJ forum

Rogal · Wysłany: Pią 15:42, 17 Mar 2006 Temat postu: E

To zadanie jest rzeczywiście takie proste czy tylko z pozoru tak wygląda?

Zapraszam do dyskusji :twisted:

jagm · Wysłany: Pią 15:51, 17 Mar 2006 Temat postu:

Sugerowałbym jeszcze odpowiedź "jeszcze nie czytałem treści, bo rozkminiam zadanie A" :] albo "jakie zadanie?"

Pandunia · Gość

[deleted]

exeman · Wysłany: Sob 1:39, 18 Mar 2006 Temat postu:

OK, no to mam ANS :P Kto zrobil i mu przeszlo? Ma ktos jakies testy? :)

Hetman · Wysłany: Nie 8:13, 19 Mar 2006 Temat postu:

heh, mi wywala TLE :( - jak ja tego nie lubie, grrrrrrr

Rogal · Wysłany: Nie 14:18, 19 Mar 2006 Temat postu:

Zrobiłem, przeszło.

Wczytuję dane na chama, do zwykłej tablicy. Żadnej dynamicznej struktury czy innego badziewia. Musiałem trochę pokombinować żeby się w limicie pamięci zmieścić, ale da się to zrobić, w sumie nawet 24MB powinno wsytarczyć. 8)

Algorytm przechodzenia robię iteracyjny (pętelka), dla rekurencji może zabraknąć pamięci.

W zasadzie jedynym problemem w tym zadaniu jest zmieszczenie się w limicie pamięci 28MB. Z prostych wyliczeń wynika, że na każdy wierzchołek potrzeba 12 bajtów (po 4 na wartość oraz lewe i prawe dziecko), wierzchołków może być max 2 mln, więc trzeba założyć zużycie 24 mln bajtów, czyli nieco poniżej 24MB. Implementując do tego zadania stos dla pętelki zużyjemy kolejne 2 mln * 4 bajty, więc w sumie będzie to prawie 32MB, więc za dużo. Nie można więc implementować żadnego stosu czy czegoś takiego bo może zabraknąć pamięci. A trzeba jakoś w pętele pamiętać "skąd się przyszło" do danego wierzchołka, żeby wiedzieć gdzie wrócić.

Ja proponuję dla porządku PreOrder przy wchodzeniu do danego wierzchołka w pętli od razu po wypisaniu jego wartości zapamiętywać jego ojca w polu, które jest przeznaczone na wartość (jako że nie będziemy już z niego korzystać bo wartość każdego wierzchołka wypisujemy tylko raz). Żeby połapać się, który wierzchołek był wypisany a który nie, zapisujemy index ojca jako wartość ujemną. Dla porządków InOrder i PostOrder ojca można zapamiętać w polu przeznaczonym na index lewego dziecka (też z wartością ujemną) - gdyż jest to wtedy pierwsze pole z którego korzystamy.

Nie wiem ktoś zrozumiał o co mi chodzi, nie potrafię dobrze tłumaczyć 8)

hansu · Wysłany: Nie 15:17, 19 Mar 2006 Temat postu:

Hmmmm, tylko z tego co nam cwiczniowiec mowil to ma byc zrobione bez dodatkowej pamiec ORAZ nie psuc drzewa... A z tego co zrozumialem to Twoje rozwiazanie robi z drzewka drzazgi :D

Rogal · Wysłany: Nie 16:25, 19 Mar 2006 Temat postu:

To fakt, robi z drzewa drzazgi

Ale w treści zadania nic nie ma o tym, że tak nie można, Rosek też nic na ten temat mi nie mówił, więc nie widzę problemu. Wszystko co nie jest zabronione jest dozwolone 8)