Informatyka UJ forum

Pandunia · Gość

[deleted]

hansu · Wysłany: Nie 22:24, 19 Mar 2006 Temat postu:

Nie byles, ale doszlismy z jagmem do wniosku ze nie bedziemy ludzi dolowac i taktownie przemilczymy pojawienie sie nowych zadan :D

jagm · Wysłany: Nie 23:02, 19 Mar 2006 Temat postu:

cóż może być bardziej wymownego od ciszy :D
no chyba że HKD :D

Fen · Wysłany: Pon 0:37, 20 Mar 2006 Temat postu:

kurcze... w tym tygodniu się postarali, dali nam te zadanka już w niedzielę... tym razem zadania sponsorują literki F i G :) na szczeście R7 już mam z głowy, ale mam jeszcze zaległości a zadaniu A ;/ coś czuję, że nie wyśpię się w tym tygodniu ;/

życzę powodzenia! :)

Rogal · Wysłany: Pon 1:09, 20 Mar 2006 Temat postu:

Jak komuś przeszło to niech się pochwali :wink: i powie jakim to sposobem zrobił. Ja próbowałem, wrzuciłem wszystkie optymalizacje o jakich była mowa w wykładzie, nie przekazuję do procedur żadnych parametrów, żadnych zmiennych lokalnych, quicksort iteracyjny, partition próbowana zarówno wersja z medianą jak i losowa, insertion z wartownikiem....

i ciągle TLE :evil:

tikan · Wysłany: Pon 1:30, 20 Mar 2006 Temat postu: G - QuickSort

A ktorej wersji partitiona uzywasz?

Rogal · Wysłany: Pon 1:44, 20 Mar 2006 Temat postu:

Teraz wogóle znalazłem jakiś algorytm Żenczykowskiego w C++ z zeszłego roku. Tam partition jest wstawiony w quicksorta i ogólnnie trochę lepiej to wygląda. Ale dalej TLE.

btw. tamten partition wybiera środkowy element, próbowałem też z losowym i medianą

Edited ok. 2:15:
Po 5 godzinach siedzenia nad kodem i 31 nieudanych próbach w końcu przeszło. Nie chcę więcej nawet słyszeć o tym zadaniu. :?

mateo · Wysłany: Pon 18:57, 20 Mar 2006 Temat postu:

kap00ch · Wysłany: Pon 19:03, 20 Mar 2006 Temat postu:

no co ty mowisz:O tylko randomized??
to ja juz 2h sie z TLE mecze i mam wszystkie optymalizacje z wykladu, a teraz lece juz 4 metode po laczonym randomizie z mediana :D :P
ewidentnie mnie nie lubi ta sprawdzara:P

mateo · Wysłany: Pon 19:09, 20 Mar 2006 Temat postu:

kap00ch · Wysłany: Pon 19:12, 20 Mar 2006 Temat postu:

najwyrazniej ma swoje sympate i antypatie :P teraz wyplula mi TLE po 4 :O minutach queued :P

ad: 18:33
MeGa LOL :O ta sprawdzara jest powalona...stosowalem miedzy innymi metode z insertionsortem...ja wiadomo insertion optymalnie dziala dla grup 8-20 elementow...jednak testy mowia co innego:P
otoz od 2h odpalalme to na testerce z roznymi warintami randomizacji ,analiz danych, liczenia median i randomizacji z medianami i analiza, w efkecie na pesymistycznym tescie mialem u siebie na kompie 5,6s i...tcs mowi TLE...w akcie desperacji zaczalem jak szlaony zemieniac liczbe od ktorej wlacza sie insert...pomimo ze u mnie czasy dramnatycznie wzrosly bo na pesymistycznym mialem juz 11s to sprawdzarka nagle powiedziala OK :O to jest wrecz nienormalne...zycze powodzenia tym ktorzy maja mniejszego farta:P

Robson · Wysłany: Pon 22:19, 20 Mar 2006 Temat postu:

Po 8 wnerwiających mocno submitach i po wpadnieciu na przyczyne moich TLE zamieszczam, taką mala podpowiedź(pewnie i tak ćwiczeniowcy to omowia jutro...no ale moze ktos chce dzisiaj miec to z glowy :) ):
do rozwiazania tego zadania wystarczą dwie optymalizacje:
1) Losowanie elementu dzielacego
2) Modyfikacja algorytmu żeby dzielił tablice na mniejsze, rowne i wieksze i zapuszczanie rekurencji(iteracji) tylko dla tych el. mniejszych i większych.

Pewnie nawet rekurencja przejdzie, chociaż lepiej na stosie - bezpieczniej ;)

hansu · Wysłany: Wto 0:30, 21 Mar 2006 Temat postu:

Wielkie dzieki, Robson!!!! Jestes wielki :D (wiem, ostatnio to wyrazenie jest mocno naduzywane :D). Ale faktem jest ze bez tego co powiedziales jeszcze dluuuuuuugo bym sie meczyl.

Spectro · Wysłany: Wto 21:51, 21 Mar 2006 Temat postu:

Ja miałem algorytm Żenczykowskiego w C++ z drobną modyfikacją przy wczytywaniu danych (losowy początkowy indeks) - taki, jaki miałem omówiony na ćwiczeniach. Przeszło w pierwszej próbie ;) .

Pawel Str. · Wysłany: Wto 22:54, 21 Mar 2006 Temat postu:

Ja miałem algorytm, który tak, jak w medianie, dzielił na 3 zbiory. Środkowy nie był już dalej sortowany. Dzięki temu w jednym kroku rozwiązywałem przypadek ciągu stałego.

exeman · Wysłany: Śro 2:04, 22 Mar 2006 Temat postu:

jesli ktos jeszcze nie zrobil G, to zapraszam na gronostaja, przed chwila dodalem testy (same skrajne i chamskie przypadki :P)

shell · Wysłany: Pią 5:46, 24 Mar 2006 Temat postu:

jak do tej pory nie potrafilem napisac najprostrzej wersji quicka to po dzisiejszych 5h umie na pamiec kilkanascie jego wariacji!!! moze i to G mialo jakis sens...:) Poszlo z mediana trzech + random i prostym wstawianiem dla n<10

Fen · Wysłany: Pon 19:10, 27 Mar 2006 Temat postu:

a ja zrobiłem: medianę z trzech, obcinanie dla małych danych (użyłem insertion sort dla < 10), randomizacja... na gronostaju mi śmiga pięknie, ale niestety sprawdzarka wywali mi TLE. No nic trzeba to jeszcze bardziej przeanalizować... ale zrobiłem wersję rekurencyjną... hmmm... może tutaj kryje się gdzieś wąskie gardło..

hansu · Wysłany: Pon 19:20, 27 Mar 2006 Temat postu:

Sama mediana z trzech nie pomoze poniewaz sa na nia pesymistyczne przypadki w testach... Musisz zrobic randomizacje i jakos sensownie obslugiwac ciagi stale... I powinno byc git :)

ostoj · Wysłany: Pon 19:33, 27 Mar 2006 Temat postu:

hmmm randomizacja + partition hoare'a + uses buffering i ok

h · Wysłany: Wto 17:17, 28 Mar 2006 Temat postu:

ale jak omijać ciągi stałe? przez pivota? można to jakoś w algorytmie hoare'a zaimplementować? ( z dwóch stron wskaźniki idą )

hansu · Wysłany: Wto 21:58, 28 Mar 2006 Temat postu:

Wedlug mnie najlepiej jest to zrobic algorytmem partition w wersji lomuto ale rozszerzonym do trzech a nie dwoch "sektorow"... Tak jak ten problem flagi holenderskiej bodajze o ktorym bylo wspomniane na wykladzie...

kg86 · Wysłany: Wto 22:37, 28 Mar 2006 Temat postu:

mi przeszlo przy randomize-partittion, nie mialem zadnych optymilizacji, okazalo sie, ze wplyw na szybkosc mialo miejsce umieszczenia funkcji randomize... wczesniej mialem ja wywolywana przy kazdym zestawie raz... a kiedy zmienilem, aby wykonala sie tylko raz, zaraz za BEGIN, to poszlo bez problemu :) mzoe mialem szczescie... ;P

Stasiu · Wysłany: Wto 23:27, 28 Mar 2006 Temat postu:

i takim o to sposobem, po 12 bombach dolaczam do grupy ludzi ktora to przepuscila :D :

random, insetrtion ponizej 20 elementow i podzial na 3 czesci (holenderska flaga) (thx hansu ;) )
chcialem z tym podzialem na 3 czesci zrobic wczesniej ale "zgubilem" jedna instrukcje przez co quick zle porzadkowal zbior a TLE dostawalem jak na koncu wlaczal sie insertion :/

exeman · Wysłany: Wto 23:30, 28 Mar 2006 Temat postu:

przekombinowales :P