USACO Januar

Eto, mislim da nije lose pokrenuti diskusiju i o zadnjem USACO takmicenju.
Ja sam ,kao, uradio sve..Prvi je 100% tacan , ideja za drugi mi je 100% tacna, a za treci ne mogu nista da tvrdim.
Ukoliko neko nije znao da uradi prva 2 zadatka , poslacu moja resenja :

Prvi zadatak :
Ovo je "well-known" problem..Resenje je u tome da za i-tu kravu pamtimo minimalnu i maximalnu visinu
do (i + 2^j - 1)-te krave.A resenje za neki interval A..B trazimo tako sto za svaki ukljucen bit u (B-A+1) na k-toj poziciji, radimo

res_min = min(res_min , minV[A][k])
res_max = max(res_max , maxV[A][k])
A = A + (2^k)

drugi zadatak
Zadatak se radi tehnikom dinamickog programiranja.Slozenost algoritma je PxM.
Resenje :

i-ti posao pokusavamo da udruzimo sa predhodnih j poslova , pa da se oni izvrse u jednom mesecu i da se nadoknada od svih prebaci u sledeci mesec.
Znaci, ako udruzujemo sve poslove od (k=i-j+1)-tog do i-tog , tu grupu mozemo ostaviti da se izvrsi nezavisno od predhodnih poslova.Tj. , da placanje pocnemo u mesecu u kome nema zaostataka iz predhodnih. Ili , tu grupu pokusavamo da izvrsimo u nekom mesecu u kome je ostao neki zaostatak..
Taj zaostatak moze biti najvise M - suma_pocetaka_iz_grupe , jer uostalom nebismo mogli da isplatimo sve..

U trecem zadatku sam radio greedy ..Slozenost je O(nlogn)..Ali , kao sto rekoh , nimalo nisam siguran za njegovu tacnost..

Ukoliko je neko uradio 3 i siguran je za ideju , bilo bi lepo da je iznese.Hvala.

Nadam se da ste razumeli ideje za prva 2.
Toliko od mene.

Pozdrav,
Relja

prvi pao na zanjem testu zbog vremena ( glupost, mislio sam da se ne moram bas skrooz paziti )..

drugi prosao skroz..E sad, u njihovoj analizi se pominju solucije cija slozenost je P^3 i P^2 * M.
A moja je PxM ..Pa ako oni ne grese, eto , moja je bolja :D

A treci je prosao samo na 2 testa..

Zeleo bih da cujem vase rezultate, pre cetvrtka :)..

Moje reshenje drugog je u najgorem sluchaju P^2 * M (mada se to nikada nece desiti), i svi primeri prolaze za 0.01 sekundu ...

a prvi ... mater mu ... :)

1 2 3 4 5 6 7 8 9 10 11 12
lineupg * * * * * * * * * *
psolve * * * x x x x x x x
schul * * * x * * x x x * * t

za 2. sam bio uvjeren da greedy prolazi... ( i josh mi nije jasno zasto pada )
za 3. sam zaboravio staviti long long ( 4 wrong answera )

prva 2 zadatka mi se uopce ne svidjaju, dok mi je 3. jedan od boljih koje sam rijesio u zadnje vrijeme... ( trebalo mi je preko sat i po da smislim O( n^2 ) rjesenje )

Sve u svemu jako razocaravajuce :)

shta znam...I meni je prvi bezveze zato sto je poznat..
Drugi mi je skroz ok zadatak..A za greedy sam mislio da nadjem kontra test, al sam zaboravio :)..
Evo, potrudicu se , pa ako stignem pre vas javicu vam..
A, ja o 3. i nisam nesto razmisljao..Prvo , intuitivno resenje, je bilo da su za duzinu d rezultati iz duzine d-1 ponovo u upotrebi..Pa onda, posto sam vec radio po nekoj tvrdoj intuiciji , rekoh da uradim i nlogn resenje po intuiciji , pa ako mi se posreci :D..Inace, slab sam sa visom matematikom.. :)

Nadam se da ce ovaj primer za 2. zad pomoci da se nadje greska za greedy :

10 3
1 8
1 2
1 1

Tacno resenje je 4 , a greedy bi trebalo da daa 5.

E, sad imam i O(P^2) resenje za 2. a to oni sigurno nemaju :)

nije neka pozadina na ovoj strani
http://ace.delos.com/TESTDATA/JAN07.psolve.htm
jel da ? :D

Sada sam shvatio zasto i meni pada greedy :(
I meni su poslednji test primeri u prvom pukli na vremenu...
Za onaj 3. sam cak mislio da imam dobru ideju, sto se i pokazalo tako za neke test primere :D

Relja, svaka ti cast za USACO :)

ja sam dosao u utorak navecer da cu to rjesavat kad ono...

ANALYSIS MODE
Submit solutions for your own enjoyment.



aaaaaaaaaaaaaaaa pogledam do kad je bilo natjecanje jer nigdje ne pise tocno i pronadjem u mail jedan neznatan dio recenice u kojem pise...do utorka ujutro

i to je objasnjenje do kad? a inace je uvijek pisao datum :(


EDIT: obavjest sam dobio u subotu kad je natjecanje vec pocelo, a do ponedjeljka nisam uopce bio na netu, a vec sam se i prije Robu zalio zasto ne najavljuje ranije natjecanja (iako znam da pise negdje na sajtu unaprijed kad su, ali zaboravim), i odgovorio mi je da objavljuje dovoljno vremena unaprijed ???