Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

E

 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych
Zobacz poprzedni temat :: Zobacz następny temat  

Jak oceniasz zadanie E?
Trywialne
16%
 16%  [ 3 ]
Średnie
22%
 22%  [ 4 ]
Trudne
5%
 5%  [ 1 ]
Po godzinie zrozumiałem jego treść
0%
 0%  [ 0 ]
Rogal to lamka :)
38%
 38%  [ 7 ]
Jakie zadanie E?
16%
 16%  [ 3 ]
Wszystkich Głosów : 18

Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysł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:


Ostatnio zmieniony przez Rogal dnia Pią 15:54, 17 Mar 2006, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  

Jak oceniasz zadanie E?
Trywialne
16%
 16%  [ 3 ]
Średnie
22%
 22%  [ 4 ]
Trudne
5%
 5%  [ 1 ]
Po godzinie zrozumiałem jego treść
0%
 0%  [ 0 ]
Rogal to lamka :)
38%
 38%  [ 7 ]
Jakie zadanie E?
16%
 16%  [ 3 ]
Wszystkich Głosów : 18

Autor Wiadomość
jagm
zielony żul



Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów


PostWysł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?"
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  

Jak oceniasz zadanie E?
Trywialne
16%
 16%  [ 3 ]
Średnie
22%
 22%  [ 4 ]
Trudne
5%
 5%  [ 1 ]
Po godzinie zrozumiałem jego treść
0%
 0%  [ 0 ]
Rogal to lamka :)
38%
 38%  [ 7 ]
Jakie zadanie E?
16%
 16%  [ 3 ]
Wszystkich Głosów : 18

Autor Wiadomość
Pandunia
Gość






PostWysłany: Pią 16:14, 17 Mar 2006    Temat postu:

[deleted]

Ostatnio zmieniony przez Pandunia dnia Pią 5:31, 10 Lis 2006, w całości zmieniany 1 raz
Powrót do góry
Zobacz poprzedni temat :: Zobacz następny temat  

Jak oceniasz zadanie E?
Trywialne
16%
 16%  [ 3 ]
Średnie
22%
 22%  [ 4 ]
Trudne
5%
 5%  [ 1 ]
Po godzinie zrozumiałem jego treść
0%
 0%  [ 0 ]
Rogal to lamka :)
38%
 38%  [ 7 ]
Jakie zadanie E?
16%
 16%  [ 3 ]
Wszystkich Głosów : 18

Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1603
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Sob 1:39, 18 Mar 2006    Temat postu:

OK, no to mam ANS :P Kto zrobil i mu przeszlo? Ma ktos jakies testy? :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  

Jak oceniasz zadanie E?
Trywialne
16%
 16%  [ 3 ]
Średnie
22%
 22%  [ 4 ]
Trudne
5%
 5%  [ 1 ]
Po godzinie zrozumiałem jego treść
0%
 0%  [ 0 ]
Rogal to lamka :)
38%
 38%  [ 7 ]
Jakie zadanie E?
16%
 16%  [ 3 ]
Wszystkich Głosów : 18

Autor Wiadomość
Hetman
pijak



Dołączył: 06 Gru 2005
Posty: 127
Przeczytał: 0 tematów

Skąd: Ustka/Kraków

PostWysłany: Nie 8:13, 19 Mar 2006    Temat postu:

heh, mi wywala TLE :( - jak ja tego nie lubie, grrrrrrr
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  

Jak oceniasz zadanie E?
Trywialne
16%
 16%  [ 3 ]
Średnie
22%
 22%  [ 4 ]
Trudne
5%
 5%  [ 1 ]
Po godzinie zrozumiałem jego treść
0%
 0%  [ 0 ]
Rogal to lamka :)
38%
 38%  [ 7 ]
Jakie zadanie E?
16%
 16%  [ 3 ]
Wszystkich Głosów : 18

Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysł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)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  

Jak oceniasz zadanie E?
Trywialne
16%
 16%  [ 3 ]
Średnie
22%
 22%  [ 4 ]
Trudne
5%
 5%  [ 1 ]
Po godzinie zrozumiałem jego treść
0%
 0%  [ 0 ]
Rogal to lamka :)
38%
 38%  [ 7 ]
Jakie zadanie E?
16%
 16%  [ 3 ]
Wszystkich Głosów : 18

Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysł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
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  

Jak oceniasz zadanie E?
Trywialne
16%
 16%  [ 3 ]
Średnie
22%
 22%  [ 4 ]
Trudne
5%
 5%  [ 1 ]
Po godzinie zrozumiałem jego treść
0%
 0%  [ 0 ]
Rogal to lamka :)
38%
 38%  [ 7 ]
Jakie zadanie E?
16%
 16%  [ 3 ]
Wszystkich Głosów : 18

Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysł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)
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych Wszystkie czasy w strefie EET (Europa)
Strona 1 z 1

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin