Informatyka UJ forum

Pawel Str. · Wysłany: Śro 17:57, 29 Mar 2006 Temat postu:

Nie precyzuję, czym jest c. To po prostu stała czasowa.
Na czym dokładnie polega ten twój algorytm countsortowy? Bo coś mi się wydaje, że na doublach to już twój algorytm nie pociągnie.

Lupus · Wysłany: Śro 20:20, 29 Mar 2006 Temat postu:

Świetny pomysł z tymi countingiem ,'] Nie wiem dokladnie jak to napisaliście, ale pewnie chodzi o takiego radixsorta, tyle ze nie trzeba nawet sortowac calych ciagow.

No, mam nadzieje ze cwiczeniowcy beda takie rozwiazania przyjmowac. Niestety w grupie mgr Brońka _trzeba_ to napisac medianą median.

Pawel Str. · Wysłany: Śro 22:57, 29 Mar 2006 Temat postu:

hansu · Wysłany: Śro 23:56, 29 Mar 2006 Temat postu:

Zgadzam se z Pawlem... Wiekszosc zadan ktore robimy i ktore maja jakies wymagania odnosnie stosowanego algorytmu moznaby zrobic jakos inaczej: szybciej, wydajniej pamieciowo, moze nawet prosciej (np. stos za pomoca stosu a nie dwoch kolejek ;)). Ale to nie o to chodzi, to nie zawody informatyczne. Te zadania sa takie, a nie inne po to, zeby nas czegos nauczyc...

domis86 · Wysłany: Czw 1:01, 30 Mar 2006 Temat postu:

Rogal · Wysłany: Czw 13:28, 30 Mar 2006 Temat postu:

To znaczy że ty mastah jesteś... :wink:

hansu · Wysłany: Czw 14:07, 30 Mar 2006 Temat postu:

domis86 · Wysłany: Czw 15:24, 30 Mar 2006 Temat postu:

exeman · Wysłany: Czw 17:14, 30 Mar 2006 Temat postu:

Doszly testy do zadania F na gronostaju, jesli bedziecie miec TLE, to pretensje do hansa za tak szybkie wzorcowki :P

trywialna · Wysłany: Czw 22:33, 30 Mar 2006 Temat postu:

Mam takie pytanko:) w tym przykładowym wejściu jest napisane ze dla ciagu 0 0 1 1 czwartym co do wielkosci jest 1 wiec chyba czegoś nie rozumiem bo moim zdaniem nie ma czwartego co do wielkosci elementu. tylko jest pierwszy i drugi...

hansu · Wysłany: Czw 22:52, 30 Mar 2006 Temat postu:

Hehe, no i znowu rozbijamy sie o definicje :D No de facto patrzac z perspektywy jezyka naturalnego to nie ma czwartego co do wielkosci elementu. Ale tu chodzi o to zeby podac co bedzie na k-tym miejscu po posortowaniu tych liczb ktore dostajemy... Po matematycznemu to sie nazywa k-ta statystyka pozycyjna (ble! okropna nazwa :) No w kazdym razie w tym ciagu ktory podalas element 4 i 3 to 1 a 1 i 2 to 0 :D

trywialna · Wysłany: Czw 23:00, 30 Mar 2006 Temat postu:

Ok to w takim razie zadam jeszcze głupsze pytanie :D jeżeli chodzi o k-te miejsce to niewystarczy napisac ze jest ono rowne tablica[k]? :roll:

hansu · Wysłany: Czw 23:07, 30 Mar 2006 Temat postu:

No ale zauwaz ze dostajesz ciag nieposortowany... A ta liczba to ma byc ta z k-tego miejsca po posortowaniu...

trywialna · Wysłany: Czw 23:12, 30 Mar 2006 Temat postu:

No tak ale moge ten ciag najpierw posortowac tak jak w zadaniu G:)

Source · Wysłany: Czw 23:17, 30 Mar 2006 Temat postu:

No ale musisz pamietac ze posortowanie całej talicy to TLE murowane. Musisz sprytnie wyszukać, w której części jest element szukany i tylko na niej wykonać partition. I dalej rekurencyjnie.
Warto też jest użyć tego ulepszonego partition z 3 częściami, które hansu podawał w poście do zadania G.

hansu · Wysłany: Czw 23:19, 30 Mar 2006 Temat postu:

No w sumie mozesz i jak masz dobrego quicksorta to Ci to nawet athina przepusci... Ale w tresci zadania jest napisane, ze algorytm ma dzialac w pesymistycznym czasie liniowym i ponadto jest napisane aby uzyc algorytmu mediany median... Wprawdzie roznie to ludzie przepychali, i quicksortem, i jakims radixem, ale mimo wszystko polecam zrobic to tym wlasnie algorytmem, chocby dlatego ze jest ciekawy, a i cwiczeniowiec Ci sie nie przyczepi ;)

Krisowski · Wysłany: Pią 12:20, 31 Mar 2006 Temat postu:

Niech to szlag... ! Na testerce mateo mam same OK i dostałem 140 punktów, a ta cholerna athina mi mówi TLE! Jak ktoś potrafi mi odpowiedzieć dlaczego to bardzo byłbym wdzięczny za tą informację.

mateo · Wysłany: Pią 12:34, 31 Mar 2006 Temat postu:

Ja podejrzewam, ze twoj program jest prawie dobry.... tylko moze sie wychrzaniac dla szczegolnych przypadkow (tzn po prostu moze sie zapetlac). Ja naprzyklad tak mialem, ze moj program dzialalo ok ale czasem (bardzo rzadko) mi sie zapetlal. Chodzilo o to ze w partition moglo sie zdarzyc, ze dokonywal on podzilu w ktorym jedna podtalblica miala rozmiar 0 - moze sie tak stac gdy jako element podzialu wezmie sie ostatni element tablicy ktory jednoczesnie musi byc najwiekszym elementem (mowa tutaj oczywiscie nie o lumoto partition), ale w lumoto tez sie tak moze stac tylko inaczej wyglada ten szczegolny przeypadek.... juz nie pamietam jak... W kazdym razie nalezy pamietac ze mediana median moze byc najwiekszym elementem w tablicy jak rowniez elementem najmniejszym i moze sie znajdywac na samym poczatku tablicy i na koncu takze. Moze to cos pomoze?

Fidel · Wysłany: Pią 19:11, 31 Mar 2006 Temat postu:

Krisowski · Wysłany: Pią 21:38, 31 Mar 2006 Temat postu:

Uff. poszło :) ... Szczerze mówiąc, to nie potrafię powiedzieć co to było. Moja pierwsza wersja korzystała z partition Hoare'a i na Virgo dostała 140 pkt (max :D ), natomiast na Gronostaju jeszcze nie dawno byłem dzięki niej pierwszy w rakingu F. Ale coż, to niestety nie zadowoliło Athiny i powiedziała, że to za wolno ;P . Przerobiłem program (a właściwie partition) na Lomuto z podziałem na trzy części (tak jak radził hansu). Co się okazało: na Gronostaju ten właśnie program dostał grubo ponad punkt mniej (to dość sporo biąrąc pod uwagę różnice pomiędzy miejscami w rankingu). Nie miałem więcej pomysłów, więc postanowiłem spróbowac na asd. Tym razem, mimo, że mój program był wyraźnie wolniejszy od pierwszej wersji, dostałem OK :shock: (przyznacie, że dziwna kobitka z tej Athiny 8) ).

A teraz wnioski :D . Zapewne rację miał Mateo. Pewnie mój pierwszy program (ten z Hoare'em) robił jakieś dziwne rzeczy dla pewnych danych :P . Niestety nie udało mi się znaleźć zestawu liczb, dla których coś nie działało. Moja rada dla tych, którzy jeszcze nie zrobili tego programu: dajcie sobie spokój z Hoare'em i zróbcie Lomuto dzielące na trzy części (trzeba trochę pomysleć w przeciwieństwie do gotowego Hoare'a, ale to się opłaci).

P.S. Dzięki za wszystkie porady, zarówno na tym forum jak i poza nim :) .

trywialna · Wysłany: Pią 21:50, 31 Mar 2006 Temat postu:

Gdzie można znaleźć ten Lomuto?

Krisowski · Wysłany: Pią 22:09, 31 Mar 2006 Temat postu:

Algorytm podziału wg Lomuto przedstawił na wykładzie dr Ślusarek. Trzeba go jednak zmodyfikować, aby dzielił tablicę na trzy części: liczby mnijesze od mediany (elementu dzielącego), liczbu równe medianie i liczby większe. Jak to zrobić opisywał hansu w poście do zadania G (przyznam, że jak dla mnie to trochę nie jasno :) , ale i tak się przydało). Jakbyś miała problemy, to mogę ci to jeszcze raz opisać (obawiam się jednak, że nie potrafię za dobrze tłumaczyć :P ).

trywialna

Madras

Ja to napsiałem czystą medianą median z Cormena i przeszło bez problemu na TCS, jedyne, na co trzeba tam uważać, to to, że cyt. "Gdyby (...) został użyty element A[r] i się okazało, że jest on największym elementem w podtablicy A[p..r], PARTITION zwróci (...) wartość q = r", co skutkuje zapętleniem SELECTa.