aOvog vikenda je (nadam se da vecina zna) bio USACO. Ukoliko ne znate neki zad ili imate neki komentar kazite.
Ja sam upravo zavrsio sa radom (za gold) i uradio sam prva dva. Treci nisam uradio (i neznam) ali se nadam da cu posle jedne partije spavanja uspeti :-). Inace, preporucio bih da procitate prva dva (pogotovu drugi). Drugi je jedna klasa dp problema koji se (koliko se meni cini) nije padao kod nas, tako da mislim da bi vecini to dobro doslo. Inace, slican zadatak je bio nedavno na TopCoder-u pa mozda je nekima i poznat.
Attach-ovao sam gold probleme ovde...
E, a ja uradio drugi i treci! :)
A sto se tiche drugog ... mislim da je takva vrsta problema jaaako chesta na topcoderu, dok se na IOI & BOI & ostalo pojavljuje jako retko (jednom kao backup zadatak by Zoran Dzunic, sledece godine kao kopija tog zadatka na CEOI, i mozda josh par puta)
Chuo sam jednu ideju za prvi ... al aj da chujem i tvoju :)
Hehe, ja uradio skoro sve :p Ono skoro je veoma bitno ;)
pa i ja sam uradio 2. i 3. Ali, 3. sam malo zeznuo u zurbi...
Nego, Rajko, jesi li u 3. radio Dijkstru , pa samo cuvao dve vrednosti ( najkrace i drugo najkrace ) ?
A , i mene zanima Andrejko kako si radio 1.
A mene zanima kako ste uradili treci :-)... Pa mislim da sam ispao kreten sto nisam uradio treci :-)... Ali sas obirom da sam takmicnje radio od 5-8 nije ni cudo sto ga nisam uradio :P
Ma prvi krenes od nazad... Zadnje si iseko oni cije su duzine najmanje (jer ces njihove duzine non-stop da sumiras pa je najabolje da su one najmanje). Zatim spojis te dve duzine, pa tako redom dok ne dodjes do kraja. Znaci cuvas duzine u Heap, izbacis dve najamnje, ubacis njihov zbir i tako dok ne dojed do kraja, ausput sabirs te gluposti :-)...
A da, sto se tice drugog jeste da se cesto pada na tc, ali je lepo da to svi nauce... Mozda se padne i na nase takm, a mozda i na neko drugo :P
Inace, Reljo, Dijkstra sa dve razlicite minmalne nece bas biti tacno. Ti od prvo do k-og mozed da dodje minimalnim putevima (istim) a od njega do n-tog razlicitim. Ja ima resenje u n * m ali nisam bas siguran. Prvo napravim graf beztezinski za koji vazi kako god se kretao od prvo do n-tog uvek idem minimalnim pute. E sad, drugi najmanji put mora da sadrzi jos neku granu (bare jednu) koja je razlicita od onih koji se nalaze tu. I to mozes da petljas u n * m...
2. je prosao a treci je pao samo na jednom testu :)..
Super je ispalo..Kao sto rekoh, znam za jednu gresku pa je to upravo ispoljeno na tom jednom test primeru...
Neka je d1[i] minimalna udaljenost cvora i od cvora 1, i dn[i] minimalna udaljenost cvora i od cvora n.
Tada za svaki par (v,w) izmedju kojeg postoji grana racunamo d1[v] + cena[v][w] + dn[w], i uzimamo minimalnu od tih vrednosti koja je veca od d1[n] ... simple as that! :)
drugi i treci prosli skroz, a prvi prosao na dva primera :)
Lepo, cestitam !
Ja prvi nisam slao, mada , mogao sam da izvucem neki testic :)..
Ja sam treci picio ovako :
Kao prvo, od nekog 2. najkraceg rastojanja do nekog cvora nikada nece ispasti neko najkrace rastojanje do nekog drugog cvora.Dok , od nekog 1. moze ispasti i 1. i 2. najkrace rastojanje do nekog daljeg..
Znaci, ako sa hipa skidam neki slog, pa ako je on 2. najkrace onda za susede proveravam samo 2. najkrace A, ako je 1. najkrace onda gledam za susede i najkrace i 2. najkrace..Ima jos par detalja, ali nebitno..
Prvi mi puko na jedan test primer (ocigledno long nije bilo dovoljno), a drugi proso :-)...
Da, inace treci moze kao sto je Rajko reko, mnogo lakse nego ovo moje (danas mu rodjendan pa ga uke... :-)
Nije me uke vec znam! :D :P
