Informatyka UJ forum

Pandunia · Gość

[deleted]

jagm · Wysłany: Nie 22:56, 19 Mar 2006 Temat postu:

to ja podpowiem, że sugerowane rozwiązanie będzie podane w notatkach sortowanie_3 :]

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

Jakby cos to dodalem do testerki generator testow do F - poki co mozna testowac w trybie 0, bo mi sie juz quota skonczyla....

swoja droga to fajnie debuguje sie to zadanko :)... naprawde mozna sie pogubic w tych wszystkich wywolaniach rekurencyjnych... mi sie naszczescie udalo to jakos przepchnac.

domis86 · Wysłany: Pon 18:58, 20 Mar 2006 Temat postu:

Ja bym powiedział tak:
Counting sort rulez :lol:

Rogal · Wysłany: Pon 21:49, 20 Mar 2006 Temat postu:

Ja wymiękam przy tym zadaniu. Znowu będzie ze 30 TLE-bomb :?

Bardzo jestem ciekaw jak wyglądają wzorcówki do zadań F,G i jak obliczają limit czasowy w oparciu o wnie. Bo o ile z moich dotychczasowych obserwacji wynikało, że średnio ambitne algorytmy bez specjalnej optymalizacji spokojnie mieściły się w czasie, o tyle dla tych zadań staję na głowie i TLE :?

Pawel Str. · Wysłany: Pon 21:57, 20 Mar 2006 Temat postu:

Ja może podpowiem, że próba kombinowania ze współczynnikiem gęstości tablicy nie działała (TLE). Należało po prostu tworzyć nową tablicę, 5 razy mniejszą (+jeden element więcej) i kopiować mediany piątek.

kap00ch · Wysłany: Pon 23:00, 20 Mar 2006 Temat postu:

a ja dla odmiany mam RD8 ;/ a na sprawdzarce mateo mam wszystko OK ;/ lipa...
swoja droga...ktos wie czemu sprawdzaramateo nie ma ochoty zapisywac testow ktore byly bledne?

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

Moze dlatego ze sie mu skonczylo miejsce na quocie??

mateo · Wysłany: Wto 0:10, 21 Mar 2006 Temat postu:

Rogal · Wysłany: Wto 1:13, 21 Mar 2006 Temat postu:

Ktoś mnie przed chwilą uratował przed chorobą psychiczną. :twisted:

W każdym razie mogę powiedzieć, że samą medianą median to raczej ciężko będzie to przejść. Polecam zastosowanie Counting Sorta dla dużych danych (np. n>100000). 8)

Robson · Wysłany: Wto 2:40, 21 Mar 2006 Temat postu:

Algorytm Hoare'a czy jakmu tam było (tego od kwiksorta). Tylko tyle powiem :)

Swoją droga jak ktoś ma kwiksorta zrobionego nie tak jak na wykładzie, tylko z wybieraniem srodkowego elementu to ma juz 70% zadania....

hansu · Wysłany: Wto 3:11, 21 Mar 2006 Temat postu:

Przykro mi to mowic Robson, ale zastosowales zly algorytm... Moze i przeszlo ale cwiczeniowiec nie powinien Ci tego zaliczyc (chociaz ja Ci tam dobrze zycze :D). Trzeba zastosowac algoytm ktory dziala w PESYMISTYCZNYM czasie liniowym, a Hoare dziala w pesymistycznym kwadratowym... Trzeba uzyc tej paskudnej mediany median...

Polecam: [link widoczny dla zalogowanych]

Robson · Wysłany: Wto 10:26, 21 Mar 2006 Temat postu:

No cóż, tak to jest jak się robi zadania do przodu znanymi ale nie Jedynymi Słusznymi Algorytmami.
Ale skoro przeszło, to chyba się za bardzo nie przyłożyli do testów, bo powinnien być jakiś na którym sie takie rozwiazanie wyłoży...
No ale, zobaczymy co dr Kawa dzisiaj na to powie ;)
Swoją drogą to zastosowałem ten algorytm, bo skoro jesteśmy przy dziel i zwyciężaj, to myslałemże o niecgo chodzi, zreszta po głowie chodziła mi jego złozonoś - 4n, ale to chyba średni przypadek... hmmmm.

Dobra to kodujcie tą medianę median, zapomnijcie o tym Hoare :)

Madras · Wysłany: Wto 12:08, 21 Mar 2006 Temat postu:

A ja polecam "Wprowadzenie do algorytmów" Cormena, s. 225 ;].

Fidel · Wysłany: Pią 20:05, 24 Mar 2006 Temat postu:

a przeszlo komus to zadanie mediana median? a dokladniej to tym algorytmem podanym przez Madrasa z Cormena?

Bo ja mam to i TLE :?

Rogal · Wysłany: Pią 21:37, 24 Mar 2006 Temat postu:

Jak pisałem wyżej polecam counting sorta dla dużych danych. Ja też miałem TLE po zaimplementowaniu algorytmu z Cormena więc to chyba norma. Inna sprawa, że ja lamka jestem i pewnie totalnie zwaliłem tą implementację ale cóż... :roll:

hansu · Wysłany: Pią 23:53, 24 Mar 2006 Temat postu:

A ja napisalem tego z Cormena bez zadnych usprawnien, bezczelnie "do konca" tlukacego rekurencja i przeszlo. I tew wcale jakos szczegolnie optymalny nie jest. Jedyne co moze go przyspieszac to partition dzielacy na trzy czesci, ale to juz chyba standard po zadaniu G :)

@Rogal: Moglbys mi wytlumaczyc jak Ty tego counting sorta stosujesz? Bo albo myslimy o roznych algorytmach albo napisales program potrzebujacy 16 Gb pamieci...

Fidel · Wysłany: Sob 0:29, 25 Mar 2006 Temat postu:

hansu · Wysłany: Sob 1:27, 25 Mar 2006 Temat postu:

exeman · Wysłany: Nie 18:58, 26 Mar 2006 Temat postu:

Czytalem ten algorytm od poczatku, od konca, od lewej, od prawej. Ale za cholere nie widze, jakim cudem mialby on dzialac w czasie liniowym!!

Przeciez nawet jesli wyznaczymy juz ta mediane median, oraz bedziemy mieli L oraz R (lewe i prawe elementy wzgledem tej mediany), to potem zeby znalesc te elementy znow trza bedzie ostro pojechac jakims polowkowym wyszukiwaniem, zatem wracamy do punktu wyjscia, jedyne co to bedziemy mieli mniejsza stala, ale rzad zlozonosci dalej niezadowalajacy (nie liniowy dla pesym.).

Gdzie mam blad w rozumowaniu, o co chodzi!

wuodi · Wysłany: Nie 22:35, 26 Mar 2006 Temat postu:

mam takie pytanie...
wlasciwie to co trzeba zrobic bo na wykladzie nie bylem? (nie z lenistwa tylkom chory byl)
Zadanie wyglada na banalne - posortowac sobie tablice i podac k-ty element a jaki haczyk?

Fidel · Wysłany: Nie 23:00, 26 Mar 2006 Temat postu:

haczyk jest taki ze ma on dzialac liniowo w pesymistycznym przypadku

polecam s.225 Cormen chociaz trzeba dodac pewne optymalizacje ktorych jeszcze mi sie nie udalo zrobic :wink:

lub jak podawal Rogal sortowanie kubelkowe

Fidel · Wysłany: Wto 23:20, 28 Mar 2006 Temat postu:

widze ze zniknely testy do tego zadania na virgo :(

mateo to tylko tymczasowo czy juz na stale?

Pawel Str. · Wysłany: Wto 23:30, 28 Mar 2006 Temat postu:

domis86 · Wysłany: Śro 14:18, 29 Mar 2006 Temat postu: