www.mimuw90.fora.pl

Maxymilian

do 36 jedyna optymalizacja jaka mi przychodzi do głowy, to, że gdy masz już odnalezioną różnicę indeksów powiedzmy 5 to potem możesz na starcie kolejnego obrotu skoczyć od razu o 5 pozycji do przodu...w pewnych sytuacjach by sie to zapewne przydalo, że tak powiem 'w realnym życiu' oraz z 'realnymi danymi wejsciowymi'

czy w 40 robicie w ten sposób, że sprowadzacie obie tablice do tej samej konfiguracji, np poprzez sortowanie? zastanawiałem się, czy nie byłoby w prosty sposób możliwe przekształcenie jednej tablicy od razu na drugą(ale nadal wykorzystując ideę sortowania) - zawsze to połowa pracy Jezyk

ale złożoność nadal tam sama

Savick · Dołączył: 18 Sie 2009 Posty: 8 Przeczytał: 0 tematów

można w prosty sposób - ale dostaniemy identyczną złożoność (tzn. robiąc tak, jak ja to widzę), aczkolwiek pewnie istnieje jakiś sprytniejszy algorytm, ale wczoraj go nie wymyśliłem, a dzisiaj mi się już nie chce:D

36 - no tak, ale chodzi mi o możliwość poprawy klasy algorytmu

mery:
(Naszą strategią jest wyznaczanie coraz większych liczb tablicy takich, żeby nie dało się zbudować trójkąta.)
Najmniejszy element ma jakąś wartość - powiedzmy b.
Załóżmy, że następny co do wielkości nie jest od niego większy i również ma wartość b.
Wówczas, kolejny co do wielkości taki, że z tych trzech nie złożymy trójkąta musi mieć wartość przynajmniej 2b (załóżmy, że ma tylko tyle).
Następny co do wielkości musiałby mieć wartość >= b+2b (przyjmijmy 3b).
Kolejny musi mieć 5b, dalej 8b, 13b, 21b itd.
Wówczas największa wartość (nazwałem ją wcześniej a) musi wynosić przynajmniej b*F_n, gdzie F_n jest n-tą liczbą Fibonacciego - jeżeli jest mniejsza, to znaczy, że w którymś miejscu jakiś element jest mniejszy od sumy dwóch elementów poprzednich (numeracja po wielkości), co oznacza że można z nich złożyć trójkąt.
Jeżeli natomiast największy element jest większy/równy od b*F_n, to nie znamy odpowiedzi - albo "za każdym razem" nie dało się złożyć trójkąta, albo w jakimś momencie się dało, a potem rosły odpowiednio szybko, by na końcu wyszło a>=b*F_n - czyli dalej mamy problem. Na czym polega korzyść? Liczby Fibonacciego rosną +- wykładniczo (wzór był podawany na którymś z początkowych wykładów, na wiki też jest), a zatem jeżeli a>=b*F_n a/b>=F_n czyli ln(a/b)>=nln(fi) (fi z daszkiem pomijamy), zatem n jest porównywalne z ln(a), czyli niewielkie, co nas niezmiernie cieszy=)

Savick · Dołączył: 18 Sie 2009 Posty: 8 Przeczytał: 0 tematów

Jak zrobić zadanie 7. z przygotowawczych? Pytam o jakieś ładne rozwiązanie, bo znając życie, tam jest gdzieś wyszukiwanie binarne do wciśnięcia, ale na razie mam tylko rozwiązanie kwadratowe...

Maxymilian

masz na myśli zadanie 7 z tą tabelką?
nie da się binarnego wcisnąć...chyba...a w którym momencie chciałbys je zastosować?
ja widzę rozwiązanie n*logn, ale tylko, gdy mamy kolejkę priorytetową działającą w czasie logn (ona jest tak jakby sybstytutem Twojego pomysłu na szukanie binarne).
na razie jednak zaimplementowałem taką, co działa n, więc całosci jest n^2.
(btw, z tą kolejką to chyba przesada, w koncu na kolosie nie ma czasu na takie rzeczy Jezyk

)

tutaj moje zadanka:
[link widoczny dla zalogowanych]

Savick · Dołączył: 18 Sie 2009 Posty: 8 Przeczytał: 0 tematów

Wie ktoś kiedy jest kolokiwum z wdp? Jedni podają 13.01, inni uważają, że to za szybko i na pewno jest 18/20...

mery

20. to by było z kolei trochę późno. 25. jest egzamin...
jedyna wersja, jaką słyszałam, to że 13.01.

Emkas · Dołączył: 22 Wrz 2009 Posty: 4 Przeczytał: 0 tematów

Czy ktoś mi dopomoże i powie jak się robi zadania typu 7,8 z przygotowawczych z drzew? Tylko tak jak dla debila proszę ;-) albo jeśli ktoś zrobił to czy się może (pseudo)kodem podzielić...

Krzysiek · Dołączył: 17 Lis 2009 Posty: 2 Przeczytał: 0 tematów

Ma ktoś dostęp do egzaminów z lat poprzednich, którymi mógłby się podzielić? Ewentualnemu "podsyłajacemu' z góry dzięki.

strop

[link widoczny dla zalogowanych]