Informatyka UJ forum

hansu

Polecam nie przeklejac quicksorta z zadania G z asd1 tylko z zadania J (tego o punktach). Otoz okazuje sie ze moj quicksort z G jako ze sluzyl do sortowania pojedynczych liczb a nie rekordow zaniedbywal sytuacje dublujacych sie kluczy (no bo dla pojedynczych liczb to nierozroznialne). Co ciekawe blad ujawnial sie tylko w losowych przypadkach (dlatego ze uzywalem randomizowanego qsorta). Co najciekawsze, IDENTYCZNY blad zrobilem w zeszlym roku przeklejajac tego durnego qsorta do w/w zadania J o punktach... ==* A mowia ze czlowiek uczy sie na bledach... :/

smas

Ja odradzam stosowanie podwójnego indexowania tab[tab2[i]]. To jest koszmarnie wolne. Miałem sortowanie tablicy index[]. Zamiast exch() po 3 tablicach => TLE x2

Madras

Thx Makros za binarke ;].

Generator testów w cpp, może się komuś przyda:

chlebek

Madras

Przechodzi też w ogóle bez elementu dzielącego. Jeśli ktoś poza mną nie ufa quicksortowi...

oinopion

ogolnie: testy nie sa perwersyjne.

kg86

ja przekleilem quicksorta z G, posortowalem wszystkie klucze wobec tego jednego i wszystko bylo ok :) srand() wywolywalem tylko raz ;)

kafex

a ja wogóle...dawałem rand()%n + 1 :P

smh · [świeżak] Dołączył: 05 Mar 2006 Posty: 21 Przeczytał: 0 tematów

Czy byłby ktoś na tyle uprzejmy i udostępnił mi zarys algorytmu do tego ćwiczenia? Byłbym wdzięczny za pomoc:-)
:prayer:

Yoter

1. Sortujemy wszystkich biorąc za klucz czas odejścia.
2. Robimy pierwszemu tyle zdjęc, ile mamy mu zrobić ( number[i] ) w chwili w której odchodzi z ławki.
3. Bierzemy następnego w kolejności sortu i obliczamy, ile jeszcze mamy mu zrobić zdjęć (być może zrobiliśmy mu już jakieś zdjęcia gdy robiliśmy je poprzednikowi) i robimy mu tyle własnie zdjęć w chwili jego odejścia z ławki.
4. Powtarzaj punkt 3. aż otrzymasz wynik.

Chyba nigdzie się nie pomyliłem, ale jeśli tak, to mnie poprawcie...

Rogal

Sam wymyśliłem inny algorytm ale zapodam ten, bo bardziej mi się spodobał :D

Będzie potrzebna struktura Zdarzenie w której pamiętamy 3 rzeczy: czas zdarzenia, jakiego agenta ono dotyczy oraz czy jest to przyjście czy opuszczenie ławeczki.

Oprócz tego mamy zmienną N określającą ilość agentów i zmienną Act określającą ile wykonaliśmy zdjęć od początku do danego momentu (na końcu będzie rządany to wynik). Będą też potrzebne 2 tablice: tablica Zdarzeń o liczności 2*N (nazwę ją Events) oraz tablica intów rozmiaru N w której pamiętamy ile zdjęć było zrobionych zanim dany agent pojawił się na ławeczce (nazwę ją PicBef).

Tablicę PicBef inicjujemy na 0, Act też na 0. Dla każdego zczytanego agenta wrzucamy do tablicy Events 2 zdarzenia - opisujące jego przyjście i opuszczenie ławeczki. Tablicę Events sortujemy rosnąco po czasach Zdarzenia. Jeśli czasy 2 Zdarzeń są równe to Zdarzenia określające przyjście agenta mają być w posortowanej tablicy przed tymi określającymi opuszczenie ławeczki. W przypadku równych czasów i typów Zdarzeń kolejność w tablicy nie ma znaczenia.

I teraz iterujemy po wszystkich zdarzeniach od 1 do 2*N. Jeśli dane zdarzenie opisuje przyjście agenta o numerze 'k' na ławeczkę to w tablicy PicBef na pozycji 'k' zapisujemy aktualną wartość zmiennej Act. Jeśli zaś zdarzenie opisuje opuszczenie ławeczki przez tego agenta to liczymy ile wykonaliśmy zdjęć gdy był on na ławeczce (od zmiennej Act odejmujemy wartość z PicBef[k]) i sprawdzamy czy to wystarcza. Jeśli nie to zmienną Act zwiększamy o tyle ile zdjęć wykonaliśmy za mało.

Po przejściu po całej tablicy Events w zmiennej Act mamy szukany wynik. :wink:

h

ten twój tester wrzuca spacje po kazdym wyniku i chwile mi zajelo zanim sie polapalem czemu diff mi wszystko wyrzuca.

exeman

Ma ktos jakis generator lub testy? Na wszystkich przykladowych i wymyslonych mam OK, natomiast Athina mowi ANS. :/

Yoter

7
1 3 2
6 7 4
6 7 5
6 7 7
6 7 20
7 7 8
8 9 15

nie wiem spróbuj czegoś takiego...

exeman

Dzieki Yoter, faktycznie, wykrzacza mi sie :)

exeman

Jakie macie zlozonosci pesymistyczne?

Spectro

@exeman:
Nie wiem i nie chcę wiedzieć ;) . Hmmm... myślę, że spokojnie za górne ograniczenie (pewnie z lekkim nadmiarem :P ) w moim algorytmie mogę przyjąć O(n*max{number[i]-number[j]}).

hansu

O(n log n)

exeman

hansu, robiles na kopcu?

Madras

nlogn ma qsort + binsearch, albo 2xqsort.

exeman

jakim cudem quicksort ma pesymistycznie nlogn?

nathaniel

Sam quicksort oczywiscie nie ma zlozonosci pesymistycznej nlogn - przeciez dobrze to wiesz!
Tylko testy nie sa 'perwersyjne' jak to okreslil oinopion :)
Powiedz jak sortujesz to moze ci cos podpowiemy. Ja zlapalem pare bombek na 'usprawnianiu' quicksorta bo wywolywalem rekurencyjnie tylko dla ciagow wiekszych niz 10 a potem wstawianie. Jak zmienilem na pelna rekurencje do samego konca to przeszlo...

exeman

No to dlatego sie was pytam o pesymistyczna a nie srednia :P
Ja walcze nad pesymistyczna nlogn. Moze do jutra zdaze, dluga noc...

kg86

ja mam O(n^2) i poszlo :)
a robilem tak:
- sortuje wszystkie 3 klucze po koncach quicksortem z randomizacja :)
- petla po wszystkich elementach - kazdemu robie tyle zdjec ile mu brakuje, i jesli brakowalo > 0, to w drugiej petli - od nastepnego do ostatniego (o ile sa w odpowiednim przedziale) odejmuje ta ilosc zrobionych zdjec...

@exeman - pesymistycznie ma n^2, ale przeciez bardzo trudno o pesymistyczny przypadek :)

Madras

No ok, masz racje, ja robilem heapsortem.