banjalukaforum.com

Ovako prvo cu objasniti metodu kojom bi che uradio zadatak pa zatim sta LSB.

Ovako da bi se izmaklo racunanje sume od kompleksnocu o(n) mozemo u nizu za svaki stoti broj upisemo cijelu sumu pa bi dobili brzinu funkcije get u najgorem slucaju od o(99) ALI za unosenje nove vrijednosti kad bi niz bio jako velik slozenost bi bila velika, tu uvodimo lsb i postavljamo slozenost uvek na o(logn)

Least Significant Byte ili LSB je posljednji bit u binarnoj repezentaciji broja. Ako je broj jedan onda je broj neparan a ako je 0 onda je broj paran. Kako to sve radi pogledajte sledeci niz:

1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64

za svaki neparan broj vrijednost je 1. za svaki broj N(N=2^X) postavljamo citavu sumu. Zanimljiv je nacin na koji to radimo (pogotovo u c-u). LSB(32) = LSB(16) * 2 = LSB(8) * 4 = LSB(4) * 8 = LSB(2) * 16 = LSB(1) * 32. Sad kako dobijemo slozenost o(logN).

Pa ovako kad upisujemo vrijednost:
Recimo da pisemo neku vrijednost na lokaciju 34. Mi cemo obnoviti sume na lokacijama = 32 + 2^1, 32 + 2^2, 32 + 2^3, 32 + 2^4(to je jednako 64 i zatim dalje zahvaljujuci lsb idemo 128, 256, 512, ....)

Pa kad vracamo vrijedost sve je isto samo nazad

Che ispravime ako grijesim, veoma je moguce

_________________
U raju je lijepo, ali u paklu je raja.

Da se nadovežem na kolezin post, LSB je least significant bit, dakle, u binarnoj predstavi nekog broja, to je "najdesniji" kec što bi se reklo, kec koji ima najmanju vrijednost. Npr:

100001 - LSB je 1
100010 - LSB je 10
111000 - LSB je 1000

U C programskom jeziku ta vrijednost se može dobiti izrazom i & -i. Kako ovo radi, pa ako uzmemo i & !i dobićemo 0 jer, ono, X and not X je False, vazda bilo

Elem, -i je tzv "potpuni komplement dvojke", ako se dobro sjećam, i njegova vrijednost je !i + 1 (eto ko nevjeruje nek proba kući). E pa da testiramo:
Broj: 01001110
Komplement: 10110001
Potpuni (+1): 10110010
And: 00000010 == LSB

E a kako algoritam radi, pa ovako nalik ovome što je Nemanja ispričao, mada, kontam, možda bi bilo najbolje da nacrtam sliku jednu pa da se pravo vidi šta se dešava Možda jednog lijepog dana

Evo recimo koja je primjena LSB-a. U Linux kernelu 2.4 korišćen je O(1) metod za kratkoročno raspoređivanje procesa, tako što je korišćen bitvektor dužine, ne znam koliko, recimo u našem slučaju da je 32 bita (jedan int, mislim kod linuksa je bio 140). Svaki bit označava da li u redu čekanja za taj prioritet postoji neki proces. Pošto prioriteti sa manjom vrijednošću imaju veći prioritet, da bi Linux kernel pronašao slijedeći proces za izvršavanje, potrebno je samo da pronađe prvi queue u kom se nalazi neki proces. Kako naći taj queue, pa umjesto da vrši ono što zovemo linearnu pretragu, postoji komanda koja nam za neki broj može reći koji je po redu njegov LSB. Tako npr ako imamo recimo samo 8 prioriteta procesa na nekom sistemu i slijedeće procese:
A - prioritet 3
B - prioritet 4
C - prioritet 4
D - prioritet 7

Onda njihov bitvektor izgleda ovako:
10011000

I jedinice predstavljaju koji su redovi (queue) puni, a nule koji su prazni. Prvi red "s desna" koji nije prazan, sadrži slijedeći proces koji treba da se izvrši na procesoru. Komanda koja vraća indeks LSB-a je mislim BLSB, ali to nije važno, poenta je da su bitovi jako moćna stvar i da to što oni "ko fol" malo optimizuju ubrzava rad cijelog sistema za neki procenat a da toga niste ni svjesni

Edit:
Inače ova "BLSB" instrukcija je ustvari "logaritam po bazi 2", bolje rečeno. Važno je kako je i implementirana ta funkcija na arhitekturi, ako radi samo kao SHR i &1 onda baš i nije neki "improvement" - pa čak i nemaju je neke arhitekture, ako sam dobro shvatio predavanja Btw, zato linux 2.6 koristi crveno crna stabla, koja nam, jel, slično prethodnom primjeru, garantuju O(logn) za pretraživanje i umetanje ključeva (prioriteta).

Sve to sto ste ispisali je super, i to sam (manje-vise) vec znao. Nego, nikako da shvatim kako primjeniti te kumulativne tabele na onaj zadatak.

Mora se modifikovati funkcija za dodavanje, koliko sam shvatio, ali ne znam kako.

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
Nikad ne zavrsim potpis do kr

Pa možda ti se samo čini da manje-više znaš...
Ajde malo se potrudi

Znate li ko sprema zadatke za BHOI i niža takmičenja u BH-RS ove godine?

Na TopCoder Open-u sam relativno brzo ispao, jebiga

Ali zato se tim Royal Air Force (RAF - Racunarski fakultet) plasirao na 8. mjesto od 174 timova iz cijelog svijeta (pretezno Evropa) na kvalifikacijama za Challenge24 2008. Pa, vidimo se u Budimpesti

PS: jedini sam "bosanac" na takmicenju, hehe

Kako ide priprema Nemanja? Dragon?

Sto se tice Challenge24 '08, pratio sam vas napredak. Poslednji put kada sam pogledao rang listu bili ste drugi, mislim da ste imali 2240 bodova, tako nesto... U svakom slucaju, svaka vam cast! Znate da vam ne zelim nista drugo osim (sad ocekujete da napisem 'srece') znanja, zato idite tamo i otkinite ih!

A sto se priprema tice... Pa nista naporno. Lagano spremamo grafove (to se radi na sekciji). A u slobodno vrijeme kuckam sta god mi dodje pod ruku. I tak'...

Najbitnije je: nisam uspio sastaviti max 3-4 dana da ne uradim makar jedan zadatak. Drago mi je sto sam tako kostantno vjezbao.

Nemanja se nesto ne javlja, izgleda nema vremena od priprema...

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
Nikad ne zavrsim potpis do kr

Nisam radio odavno. Trenutno sam bolestan

_________________
U raju je lijepo, ali u paklu je raja.

Jes' nam mrtva tema....

15. 3. ove godine se održalo regionalno takmičenje srednjoškolaca. Igrom slučaja i ja sam učestvovao. Rezultati su bili očajni, imao sam čitavih 5 bodova od mogućih 100, ali i to je (vjerovali ili ne) bilo dovoljno da zauzmem 5. mjesto... Kako ovo bezze zvuči...

Evo za 2 sedmice (28. marta) će nam regionalno iz programiranja. Spremamo li se, ostali? Gdje su nam takmičari? Niko se ne javlja, svi vježbaju, jel?

Što se tiče republičkog i državnog, čuo sam da će se jedno održati u Sarajevu a drugo u Doboju, najvjerovatnije. A ko sprema zadatke - ne znam.

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
Nikad ne zavrsim potpis do kr

Miroslav B. iz Matematicke gimnazije je osvojio 6. mesto na TopCoder HighSchool takmicenju i 800$ nagradu (uz put u Ameriku)! Eto kako ljudi ovde cepaju

Oho.... Koji je Miroslav razred?

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
Nikad ne zavrsim potpis do kr

Sad sam se vratio sa regionalnog "takmicenja" iz programiranja. Svaka cast organizaciji... Nemam rijeci.

Prije nego sto iznesem utiske, interesuje me samo koji kralj je na Banjaluckoj regiji imao 85 bodova?

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
Nikad ne zavrsim potpis do kr

Kakvo je to bilo takmicenje. Nesto su rekli kao za elektro skole, a regionalno je 28. Mozes li malo opsirnije i kakvi su bili zadatci.

I danas je bilo opstinsko takmicenje iz programiranja OSNOVNI skola u Gradiskci. Ja i Vilic smo bili u komisiji. Zakljucak bruka. Ne mogu svatiti da je neko dosao na takmicenje a da nije znao uraditi prvi zadatak.

Zadataci (prepricane verzije ):

1. Naci proizvod brojeva od K do N koji se se unose: pr. ulaz: 2, 4 izlaz: 24
2. Unose se dva broja i znak (+ - * /) i treba odrediti vrijednost izraza: ulaz: 10 5 + izlaz 15
3. Sortirati niz.
4. Ulaz: NADA
Izlaz: NADA
A D
D A
A N
NADA

_________________
U raju je lijepo, ali u paklu je raja.

Da li neko zna koliko ima elektrotehnickih skola u RS, tj. koje su skole ucestvovale na regionalnom i kada ce i gdje biti republicko (samo elektrotehnickih)?

Sto se tice takmicenja, blago receno - sramota.

1. zadatak (35 bodova):
Spiralni obilazak matrice, ali ovoga puta (za razliku od prosla dva) u smjeru suprotnom od kazaljke na satu. Smijesno...

2. zadatak (35 bodova):
Unosi se tablica permutacije T, a treba naci permutaciju P kojoj ta tablica odgovara, uz zadavanje uslova da li su brojevi lijevo od i veci ili manji.

3. zadatak (30 bodova):
Dat je neki ogroman broj od 15 cifara koji ima svojstvo da kada se pomnozi sa nekom od cifara [1,9] daje isti taj broj ciklicno pomjeren u desnu stranu za K mjesta. Postrebno je ispisati decimalni oblik heksadecimalnog broja X9, X8, X7, ... , X2, X1, gdje Xi predstavlja K kada se dati broj pomnozi sa i. (inace, program nema ulaz)

Nijedan test primjer za drugi zadatak nije bio tacan!!! Naime, po zvanicnim rjesenjima bilo je potrebno na izlazu imati "0011601" (ili nesto slicno) a trazi se permutacija niza 1,2,3...,n-1,n!!! Kako permutacija elemenata od 1 do n moze da sadrzi nulu, i to ponovljenu??? Ili recimo treci zadatak... Niko ziv nije shvatio sta se trazi u zadatku osim mene. I ja uradim zadatak, ali cik pogodite.... Ni to rjesenje se ne poklapa. A 101% sam siguran da je tacno, jer sam pjeske izracunao trazeni broj i dobio poklapanje sa izlazom programa. Neka, nije moja sramota....

Ja sam dijelio 1. mjesto sa skolskim, a svih ostalih 8 takmicara je dijelilo 2. mjesto sa osvojenih 0 bodova.

Bruka, najblaze receno...

I ja stvarno ne znam koji lik moze, pored onako definisanih test primjera, imati 85 bodova... 'Ajde neka se javi ili se vi momci iz Banjaluke raspitajte ko je on i odakle mu zadaci. Stvarno je smijesno ovo sto se desava...

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
Nikad ne zavrsim potpis do kr

Jbg. tako ti je to. Jel bilo sta za jesti. Ja danas pecenje (za komisiju ) po otisao u svoju skolu gdje je bilo takmicenje masinaca pa opet pecenje.

1. Zad. Trebalo im je 5-6 godina da se sjete obrnuti smjer
2. Nisam bas skontao, jel ti dobiras tabelu ili npr. 1, 2, 3 , 4 ,5 i trebas naci 10 permutaciju
3. Fizicki posao

_________________
U raju je lijepo, ali u paklu je raja.

zasto mi se cini da se oni sa etf-a opet petljaju u smisljanje zadataka iz programiranja...umjesto da se okrenu popravljanju pegli, sto im ide mnogo bolje

_________________
Zec: NEEEEEEE, RISE!
Ris: Ma ne remse!

Za jesti? Hamburgeri, cevapi i sl... Ali samo 1 po osobi.

A sto se zadatka tice, unosi se tablica permutacije, npr. 012 a permutacija niza {1,2,3} kojoj odgovara ova tablica je {3,2,1}, jer redom imamo:
- 0 elemenata vecih od prvog
- 1 element veci od drugog
- 2 elementa veca od treceg

Ne mogu da objasnjavam sada detaljno, kada u ponedeljak dobijem zadatke prekucacu ih. Zajedno sa test primjerima, naravno... Gdje to da propustim? Slag na torti....

Mozda da otvorim neku novu temu u forumu "humor", prikladnije je...

_________________
Pretpostavka: Ljudi ne bi trebalo da rade, vec da se zezaju.
Dokaz: Majmun se citav zivot zezao i od njega je postao covjek!
Nikad ne zavrsim potpis do kr

Prekucaj bas me zanima. Inace Ja se i ove godine takmicim u BL. Moja skola dolazi sa cetiri takmicara. Ja, Ivanovic i dva mladja(ne znam kako se zovu bili su prosle godine, sjecam se da je jedan nosio kolace) i naravno moj profesor i najvjerovatnije Vilic. Nadanja su: Da ce 3 zadatka(nedami se kucati 4 zadatka) da cu imati dovoljno bodova za republicko, da ce biti cura, da cu se napiti i to je to

_________________
U raju je lijepo, ali u paklu je raja.