banjalukaforum.com

Pa kad granica dozvoljava glupo resenje, najgluplje resenje je ustvari najbolje. Inace, ovakav zadatak se radi dinamickim programiranjem.

Kazem da je neocekivano da nema. Ocekivao sam bar 8 takmicara sa po 100 bodova. A sto se tice resenja sasvim dobro radi, jel predlazes da sam trebao kucati DP alogritam i izgubiti 20min na zadatak umjesto ovako manje od 60 sec

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

Nemanja, mislim da je Milanko Djeric mene pitao za te bodove (i gimnaziju).

Ne kazem da je uopste neocekivano da gimnazijalci imaju dobre plasmane na takmicenjima iz programiranja, vec da je to na regiji BN rijedak slucaj. Tehnicka skola je inace poznatija po intenzivnijim pripremama takmicara za tu disciplinu. Evo, npr, u gimnaziji se cak i ne odrzava sekcija iz programiranja, a Pascal se radi samo dva polugodista i to u razlicitim razredima, ali za onakve zadatke je to sasvim dovoljno (pokazalo se).

A za taj zadatak se i ja slazem sa Nemanjom i Sreckom. Nakon prvog citanja pada na pamet rekurzija ( http://www.bhoi.net/zadaci/rastava.htm ), nakon 5 sekundi u glavi vec imas sliku te tri for petlje i blagi osjecaj zadovoljstva, znajuci da je to sasvim dovoljno. Nakon 2 minuta imas gotov program i zelju da predjes na drugi zadatak. Simple as that.

_________________
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

E, da, zaboravio sam da pitam Srecka: zar se ovo moze raditi dinamickim?

Mogu se izbrojati razliciti ishodi bacanja, a kako si mislio da ih pronadjes DP-om?

_________________
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

Pogledaj zadatak Mars sa BHOI-a.

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

potpuno pogresan pristup rjesavanju zadataka. najgluplje rjesenje je vrlo rijetko najbolje. a pogotovo kad tek ucis programiranje, pa pocnes da govoris 'ma nema veze, uradicu ovaj zadatak na prvi nacin koji mi padne na pamet'. i onda budes sav srecan jer su
ti neki, cije je poznavanje algoritama najblaze receno upitno, dali 100 bodova na takva rjesenja i smatras se veoma umnim i smijes se 'nekim glupacama iz kostajnice kojima je to bilo pretesko'. pa onda kad dodjes na ozbiljnija takmicenja gdje zadatke daju ozbiljniji ljudi koji se malo bolje razumiju u algoritme, ispusis ga. to sve govorim iz licnog iskustva. razlika u takmicenjima na nivou rs i bih i, recimo, tipa olimpijade ili ACM takmicenja je ogromna.

btw, zadatak nema nikakve veze sa dinamickim programiranjem. dp se koristi u problemima optimizacije, kada se trazi optimalno rjesenje nekog problema, i kad optimalno rjesenje problema u sebi sadrzi optimalno rjesenje potproblema. sa cim ovaj problem nema nikakve veze.
takodje, ni rekurzija ovde nema nikakve veze. rekurziju treba da izbjegavate kad god je moguce, jer, ako se ne postupa oprezno, lako mozete da zavrsite sa algoritmom eksponencijalne slozenosti.

da je autor pomenutog rjesenja razmislio 5 sekundi vise o svom rjesenju, vidio bi da nema potrebe da vrti for petlju po k, zato sto ako je Sum konstanta, a vec ima zadato i i j, i ima uslov i+j+k=Sum, onda je ocigledno k=Sum-i-j. dakle, samo je trebalo provjeriti da li je Sum-i-j>0 i Sum-i-j<7 i, ako jeste, ispisati i,j,Sum-i-j. cime se ustedi jedna for petlja, i da je granica umjesto 6 bila n, dobio bi se algoritam slozenosti n^2 umjesto n^3, sto je ogromna razlika.
dakle, manje pametovanja o svojoj genijalnosti i gluposti drugih, i manje samaranja pojmovima kao sto su 'dinamicko programiranje', 'greedy algoritmi', 'rekurzija' ako ne znate tacno gdje se koriste...jer, kolko god neko za sebe misli da je pametan, postoji mnooogo ljudi koji su beskonacno puta pametniji od njega. ali, ta spoznaja dolazi sa odrastanjem

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

Tvoje konstatacija je pogresna. Tako bi se ispisale i permutacije. I sad sta bi bilo brze pitanje jer bi imao vise uslova koje takodje uzimaju procesorsko vrijeme. Zaboravio si uslov Sum - i - j >= j Pitam se kako ti dade sve bodove na netacan zadatak kod nas su se oduzimali bodovi ako se ispusuju permutacije. Inace otkud tebi ideja da se ja hvalim?

Zelis reci da je moje poznavanje alogoritama upitno? Ja se nebih slozio sam tim a mislim i jos neki na ovom forumu.

TheDragon. Sa dp-om radis tako sto pravis tabelu broj_kockica * suma.

I da zaboravi. A kako da se ne smijemo ljudima koji su dosli na regionlno takmicenje a ne znaju uraditi najosnovnije stvari.

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

da, zaboravio sam u brzini da napisem da treba i taj uslov. vrlo dobro opazanje inace, uopste nije pitanje koji algoritam je efikasniji, ali ce proci jos mnogo vremena prije nego sto budes radio analizu algoritama i budes shvatio zasto se to pitanje uopste ne postavlja.

btw, ja sam svoja takmicenja zavrsio prije nekih 10 godina. veoma uspjesno za lokalne bih prilike i veoma neuspjesno za sire prilike, jer sam na srbijanska (u moje vrijeme su najbolji iz rs isli u srbiju na savezno takmicenje, koje je bilo izborno za olimpijadu) i, kasnije, inostrana (ACM) takmicenja isao sa mislju da sam veoma pametan, jer sam bio najbolji u RS, i da zadatke upravo treba rjesavati na prvi nacin koji ti padne na pamet jer, zaboga, ko bi gubio vrijeme na razmisljanju o rjesenjima kad lokalni pregledaci ionako ne znaju nista, pa ce mi dati sve bodove, jer zadatak radi. pa onda, kad si u konkurenciji najboljih u regiji (jer je, recimo, u vrijeme kada sam ja isao u srbiju na savezna takmicenja, na istim takmicenjima nastupao najuspjesniji srbijanski olimpijac svih vremena iz informatike, jaroslav blagojevic, koji je osvojio dvije zlatne olimpijske medalje, od toga je jednom bio treci na olimpijadi), onda vidis kako je tvoje poznavanje, za koje si bio siguran da je jako veliko, ustvari veoma malo.

ne zelim reci da je tvoje poznavanje algoritama upitno. zelim reci da je tvoje poznavanje algoritama NULA. sto ne treba da te sikira, jer prije 2-3 godine fakulteta i dosta ucenja matematike, i ne mozes da imas nekog pojma o algoritmima. ali, ako se budes trudio, i ako u odredjeno vrijeme shvatis koliko ne znas i dobijes zelju da ucis, sve ce biti u redu

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

Dragon: moguće, nisam ni pročitao zadatak

Nemanja: pa, vrlo je upitno

Milanko: Kad su takmicenja u pitanju, n^3 je mnogo veće od n^2, ali za n = 1000, dok za n=6 nije.

a kako da se ja ne smijem nekome ko uporno prica da se neki zadatak rjesava dinamickim programiranjem, a da ne zna uopste sta je dinamicko programiranje i u kojim problemima se koristi? no, opet ti kazem, ne sikiraj se, jer prije fakulteta ne mozes razumjeti sta je ustvari dinamicko programiranje. btw, dio 'programiranje' u 'dinamicko programiranje' nema veze za programiranjem u nekom programskom jeziku, nego je isto kao i u oblasti 'matematicko programiranje', tj. oblasti matematike koja se bavi optimizacijama.
dakle, opet ponavljam, manje price o svojoj pameti i smijanja drugima. kako rece koja na albumu discipline kicme, 'ego je, vjeruj mi, tvoj neprijatelj najveci'

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

Hahhaaaaa, ovo je za citirati

che, prijatelju stari, razlika izmedju algoritama slozenosti n^3 i n^2 je ogromna. naravno, u konkretnom slucaju, posto je gornja granica 6, svi algoritmi imaju slozenost koja je konstanta, tako da su sa analitickog aspekta, svi jednaki.
ja samo kazem da ako je nekom jedino bitno hoce li mu ljudi koji se ne razumiju u algoritme dati 100 bodova na takmicenju ili ne, i ako ne razmislja ni sekundu o jednostavnim stvarima nego rjesava zadatak na prvi nacin na koji mu padne na pamet, postoji velika vjerovatnoca da ce mu se isto desiti i kada su u pitanju mnogo ozbiljniji zadaci. a tu je razlika u ovim 'detaljima' presudna.
sad, hocete li vi to shvatiti kao moje pametovanje ili ne, to je vas problem. ja sam samo tu da dam savjet
takodje, savjetujem citanje knjige 'introduction to algorithms : a creative approach' od autora udi manber-a, gdje se upravo polazi od najociglednijih rjesenja i analizira se zasto ona nisu dobra, pa se poslije popravljaju.

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

Znas vrijedjati to je ocito. Ovde mi predlazes da radece rijesenje zamjenim neispravnim(prvo tvoje predlozeno je bilo netacno i nije mi jasno da neko ko tvrdi da jako dobro poznaje materiju tako grijesi), sta je glupo. Moje resenje je upotpunosti tacno. Ovde pricas kad bi bilo onda bi ... jer mislis da bih ovako rjesavao zadatak kad bi bilo ...

Drugo, nisam se hvalio da sam najpametni niti da sam bolji od vas sviju (sta sam napisao za dvije cure to stoji), to je radio neko drugi. Da je moje znanje jednako NULA to je tvoje misljenje. Ja sa bavim programiranjem ne psihologijom pa ne mogu zakljuciti kako je tvoje iz 3-4 posta, to cu ostavati "pametnim".

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

uf, opet moram da prokomentarisem 'radece' rjesenje za jednostavan problem uopste nije tesko napraviti. u mom 'neradecem' rjesenju (neveliko cudo, s obzirom da nisam vidio text zadatka, nego sam na osnovu tvog rjesenja zakljucio sta se trazi) je potrebno modifikovati samo jednu sitnicu (tj. dodati jos jedan uslov). problem je sto bi ti, vjerovatno, na isti nacin rjesavao zadatak i da je umjesto 6 bilo n, koje se unosi (jer je, pobogu, to ono sto 'prvo padne na pamet'). i tako bi dobio potpuno neefikasno rjesenje, sto bi ti lokalni pregledaci priznali, jer, pobogu, radi.
ja ti upravo i govorim da ce te princip 'zasto bih trosio vrijeme analizirajuci nesto sto radi' dovesti do neuspjeha na ozbiljnijim takmicenjima. jer ces i tamo pokusati da rjesis zadatak brute force metodom, kao ovde, potrosices ogromnu kolicinu vremena na to, i na kraju ces dobiti nesto sto ili nece raditi, ili ce raditi samo za male velicine unosa. a tamo kriterijumi nisu 'aha, ovo radi za dva unosa. super, evo mu svi bodovi'. opet ti kazem da sve ovo govorim iz licnog iskustva. ako na lokalnim takmicenjima 'stedis' svoju pamet za neka veca, i ako mislis da je sasvim dovoljno sto si nesto 'rijesio i radi', i da ces o problemima koji mogu nastati sa takvim rjesenjima razmisljati u tezim zadacima, to je najsigurniji put za neuspjeh

sto se tice tvog poznavanja algoritama, ono je, sasvim sigurno, apsolutna nula. ne zbog toga sto si glup (to nema veze sa pamecu), nego iz prostog razloga sto mnoge stvari vezane za to ne mozes da razumijes dok ne sazres do odredjenog stepena.
u srednjoj skoli jednostavno ne mozes da razumijes teoriju algoritama, jer nemas dovoljno predznanje za to. to se stice tek u visim godinama fakulteta. kada budes naucio mnogo matematike, kada budes ucio o analizi algoritama, i onda ces shvatiti zasto je recenica 'pitanje je koji od ova dva algoritma je bolji, jer ovde ima jedan uslov vise koji se provjerava' smijesna. takodje, shvatices da dinamicko programiranje nije samo 'aha, napravi matricu, upisi nesto u nju, kombinuj neke vrijednosti iz nje i super', nego da ima veze sa problemima optimizacije, i da moraju da budu ispunjeni odredjeni uslovi da bi se zadatak mogao rjesavati tom metodom. a matrice su tu samo pomocno sredstvo.

cinjenica da ja znam neuporedivo vise o algoritmima od tebe (mada, naravno, ima ljudi koji znaju neuporedivo vise od mene) je jednostavno posljedica cinjenice da sam 10 godina stariji od tebe, da sam zavrsio nesto malo vise skole od tebe i citao mnogo vise o tome iz ozbiljne literature.

nadam se da su ti sada stvari nesto jasnije

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

Koji vrag da radim na optimizaciji kad zadatak radi ono sto treba. Niko na takmicenju ne pregledava kod (ni na medjunarodnim, sta bih znao ako si ucestovao na njima) nego trebas da ispises tacan rezultat u okviru nekog vremenskog i memoriskog ogranicenja. Vidim da si naucio sa tim knjigama da podcjenjujes ljude. Znam da nisam "bog" iz alogoritama ali znam isto tako da nisam neko ko nezna ni sta je to. Znam dobro koliko kod naucim znacu samo jedan mali postotak. Siguran sam sto budem sve vise ucio znacu vise. Sa svojim znanjem sad mogu da konkurisem za 1. mjesto u BIH (mozda malo pretjera ) ali znam da na IOI sigurno ne mogu.

Hvala tebi na velikom savjetu kad bude drugi zadatak uradi drugacije. Tvoj je jedini cilj bio da nekog pokusas napraviti glupim, bas lijepo od tebe.



A sta onda pametujes kad nisi vidio.

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

Pa ne mora da znači, šta više, ako čovjeku regionalno nije izazov, što bi mrsio muda umjesto da što prije odradi posao i ode kući...


Naravno. Prerana optimizacija je koren svakog zla Hoare, Car (C.A.R.)

Tako je, osim što na našim takmičenjima Fuad pregledava kod i s**e kvake (ne može ova funkcija, ne može ovo, ne može ono itd uglavnom ja najebem uvijek).

Hehe zar pored mene zivog

Pa mislim da se iz aviona vidi da nisi morao da pišeš tri petlje...

Nije to nego zurio sam se u WC.



Otkad te nema vise nepregledava



Mislim na BHOI



Pa vise se vidi u drugom kako sam trazio proste brojeve

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

Ucesnici na republickom takmicenju iz programiranja:

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

Gdje ce biti takmicenje i koliko prolazi dalje? Nisam od regionalnog radio nista u vezi programiranja, imao sam juce republicko iz matematike. Kog tipa su zadaci na republickom i da li se trazi poznavanje nekih posebnih oblasti (u odnosu na regionalno (ne mislim na ovogodisnje regionalno (jer su zadaci bili prelagani (a ja opet izgubio 10 bodova)), nego na proslogodisnja))?

Ma bice ko na regionalnom.
Takmicenje je u subotu u Doboju.

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