[es] - Zadatak sa pakovanjem vremenskih intervala

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
c-bg-d-p6-68.BVCOM.NET.

+1064 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{30.10.2008. u 14:19 - pre 188 meseci}

Jesi ti proverio da li ovo radi ;) a radi.

Tacno je to sto kazes ali sve zavisi od nacina kako kodiras.
Fora je da a*m+b bude tako da uvek a<=m/2 i b<m

Sta mislis jel sam ovo poslao napamet ili sam prvo proverio da li radi ;)
Nego logika mi govorila da ovo moze sa O(1) samo sam trebao da uhvatim
pravilnost ;)
Ako ti nije jasno objasnicu u sledecem postu.
Drugo, ne kapiram sta podrazumevas pod time pocetak posle kraja?valjde je uslov da interval a,b bude takav da a<=b ili ne?
Pa ni tvoje niti bilo koje drugo resenje ne radi u tom slucaju zato sto sa 64 bita
*ne mozes* pokriti te slucajeve jer onda imas n^2 a ne n(n+1)/2 mogucnosti ;)

Pozdrav!
edit: sto se tice kompleksnosti algoritma tvoj za dekodiranje ima O(log n) kompleksnost a ne O(1)

_{[Ovu poruku je menjao Branimir Maksimovic dana 30.10.2008. u 15:45 GMT+1]}

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.

+2790 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{30.10.2008. u 16:27 - pre 188 meseci}

Proverio sam tvoj algoritam i ima samo jedan lako otklonjiv nedostatak: Izasao si iz 64-bitne aritmetike. Kada je start blizu pocetka, a stop blizu kraja, imaces prekoracenje (s1+s2 je oko 3*m/2). No, to se moze srediti racunanjem u 128-bitnoj aritmetici.

Svaki algoritam koji ima konacan broj mogucih vrednosti na ulazu ima slozenost O(1). Ovde mogucih vrednosti na ulazu ima n=18356099197581849600 mogucih vrednosti na ulazu. To su celi brojevi od 0 do n-1. Neka je v(x) vreme potrebno za dekodiranje vrednosti x (ceo broj od 0 do n-1). Vrednost v=max_xv(x) je konacna kao maksimum konacnog skupa konacnih vrednosti. Kakav god da je ulaz, ne treba ti vise od v vremena (a v je konstanta) za dekodiranje, pa je to svakako O(1), bez obzira na algoritam (ukljucujuci i najgrublju silu).

No, svakako da imam log₂(n) iteracija, ali, strogo govoreci, kod nas je n konacno, pa je i broj mojih iteracija ogranicen (na 64), tako da je svakako O(1). Medjutim, ako smatramo da je n nesto mnogo veliko, onda smatramo moje vreme logaritamskim po n, mada je strogo matematicki govoreci ograniceno.

No, tvoj algoritam je svakako bolji. Svaka ti cast! Tesko bih se ovoga setio.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.

+2790 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{30.10.2008. u 16:30 - pre 188 meseci}

Citat:

Branimir Maksimovic: Drugo, ne kapiram sta podrazumevas pod time pocetak posle kraja?valjde je uslov da interval a,b bude takav da a<=b ili ne?
Pa ni tvoje niti bilo koje drugo resenje ne radi u tom slucaju zato sto sa 64 bita
*ne mozes* pokriti te slucajeve jer onda imas n^2 a ne n(n+1)/2 mogucnosti ;)

Tacno. Zato se taj uslov mora iskoristiti da bi se sve spakovalo u 64 bita (tj. moraju se odbaciti parovi kod kojih je pocetak posle kraja, koji su besmisleni, da se ne bi kodovi trosili na njih). To je caka koju sam imao na umu kada sam postavljao zadatak.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
195.222.97.*

+2790 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{30.10.2008. u 20:20 - pre 188 meseci}

Citat:

Nedeljko: Proverio sam tvoj algoritam i ima samo jedan lako otklonjiv nedostatak: Izasao si iz 64-bitne aritmetike. Kada je start blizu pocetka, a stop blizu kraja, imaces prekoracenje (s1+s2 je oko 3*m/2). No, to se moze srediti racunanjem u 128-bitnoj aritmetici.

Može se ispitati dali je s1+s2>=maxDateValue i unutar 64-bitne aritmetike.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
c-bg-d-p6-68.bvcom.net.

+1064 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{30.10.2008. u 20:38 - pre 188 meseci}

s1+s2 == max 34 bitni broj ;)

probaj za sve vrednosti i videces da radi. ;)
nema nikakve 128 butne aritmetike.
No kapiram tesko je poverovati da ovo radi, ali radi ;)

Pozdrav!

edit: i jos jedan pozdrav i hvala na zadatku, da malo razbijem monotoniju dnevnog posla ;)
sto se tice kompleksnosti na input od n elemnata binary search daje O(log n) kompleksnost
bez obzira sto je n fiksno u nasem slucaju. Medjutim u zavisnosti od inputa
imas minimum 1 a maksimum log n iteracija. Zbog toga se tako kaze cini mi se.

_{[Ovu poruku je menjao Branimir Maksimovic dana 31.10.2008. u 02:51 GMT+1]}

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.

+2790 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{31.10.2008. u 08:00 - pre 188 meseci}

Ako je n konstanta, onda su O(n) i O(log n) isto sto i O(1). No, razumeli smo se.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.

+2790 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{31.10.2008. u 11:16 - pre 188 meseci}

U pravu si bio da nema prekoracenja. Sve je u 64-bitnoj aritmetici.

Nego, da li bi mogao da napravis uopstenje ovoga? Recimo, kodirati parove (x,y) tako da je 0<=x<=y<n vrednostima 0,...,n*(n+1)/2-1. Rekao bih da u slucaju y-x>n/2, mozes svoji algoritmom da dobijes kodove koji nisu manji od n*(n+1)/2. Takodje, resavao si slucaj kada je n parno. Neka n bude proizvoljan priridan broj.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Branimir Maksimovic

Član broj: 64947
Poruke: 5534
c-bg-d-p6-68.BVCOM.NET.

+1064 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{31.10.2008. u 18:54 - pre 188 meseci}

Mislim da ovo resenje radi i za parne i neparne maximalne vrednosti.
U pocetku sam stavio originalni uslov s1+s2>max sto je pokrivalo samo parne
ali sa s1+s2>=max pokriva i neparne max.
Da u pravu si maximalna vrednost je n(n+2)/2 - 1 ali sa obzirom da celobrojno deljenje
skrati n/2 za 1 bit to se svodi na k(2k+2) sto je k(n+1) gde je n == 2k+1 u slucaju neparnog.
A u parnim slucajevima ovo ne prelazi 64 bita posto je max neparni.
Da je max paran broj ovo ne bi radilo.
E tu sad stoji jedno interesantno pitanje: jel max neparan slucajno ;)?

Pozdrav!

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
195.222.97.*

+2790 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{01.11.2008. u 20:38 - pre 188 meseci}

Još jednom, sve čestitke za briljantno rešenje.

Šaljem rešenje za opšti slučaj u PDF formatu.

P. S. Kada je n veliko, tj. izlazi iz opsega ugrađenih tipova, pa se mora koristiti aritmetika u proizvoljnoj tačnosti, naša rešenja imaju, do na O (tj. do na konstantan faktor) istu složenost, ali o tome ću neki drugi put.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Prikačeni fajlovi

kodiranje.pdf - 47.56k

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.dynamic.sbb.rs.

+2790 Profil

Re: Zadatak sa pakovanjem vremenskih intervala

^{03.11.2008. u 10:55 - pre 188 meseci}

Pretpostavimo da je n(=broj mogucnosti za trenutak) jako veliko, tj. da daleko premasuje opsege ugradjenih tipova, pa da se mora koristiti aritmetika za racunanje u proizvoljnoj tacnosti. U toj aritmetici, (sa najbrzim poznatim algoritmima) slozenost racunskih operacija iznosi:

- O(n) za sabiranje i oduzimanje, kao i za mnozenje i delenje malim vrednostima (koje su unutar opsega ugradjenih tipova), npr. sa 2 i za poredjenje (u najgorem slucaju),
- O(n log(n)) za mnozenje,
- O(n log²(n)) za delenje, kao i za korenovanje proizvoljnog stepena.

Moj algoritam za kodiranje ima dva sabiranja, jedno mnozenje i jedno delenje sa dva, odnosno slozenost O(n log(n)). Moj algoritam za dekodiranje ima O(log(n)) iteracija koje ukljucuju poredjenje, sabiranje, mnozenje i delenje sa 2. Znaci, iteracije imaju slozenost O(n log(n)), ali posto iteracija ima O(log(n)), cela petlja ima slozenost O(n log²(n)). Nakon toga imam fiksan broj mnozenja, sabiranja, oduzimanja i delenja sa 2, pa je O(n log²(n)) ukupna slozenost algoritma.

Branimirov algoritam za kodiranje ima slozenost O(n log(n)) jer ukljucuje fiksan broj sabiranja, oduzimanja, delenja sa 2, mnozenja i poredjenja. Algoritam za dekodiranje ima fiksan broj operacija, od kojih je najzahtevnije delenje (za izracunavanje vrednosti s1), pa ima slozenost O(n log²(n)).

Dakle, ovako posmatrano, slozenost oba algoritma je ista do na konstantan faktor. Medjutim, ako treba izvrsiti veliki broj kodiranja i dekodiranja sa istom vrednoscu n, onda se veliki broj delenja sa uvek istom vrednoscu moze vrsiti sa slozenoscu O(n log(n)) po delenju, pa u tom slucaju (ako program radi uvek sa istom vrednoscu za n, koja se jednom zadajen na ulazu u program), onda je Branimirov algoritam brzi, tj. ima slozenost O(n log(n)).

Sa druge strane, unutar opsega ugradjenih tipova, jeste da se delenje vuce ko mrcina u poredjenju sa drugim operacijama, ali je ipak brze od moje petlje, jer je hardverki implementirano.

Jos jednom, sve cestitke za Branimira.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu