Algoge Judge

Editorial for Vodopad

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Analiza

Najpre ćemo objasniti rešenje koje radi u složenosti $O(n^2 \cdot h)$ ~O(n^2 \cdot h)~, što je dovoljno da se osvoji 70 poena, a zatim ćemo pokazati kako se to rešenje može jednostavno izmeniti tako da radi u složenosti $O(n \cdot h)$ ~O(n \cdot h)~ i donese 100 poena.

Rešenje u $O(n^2 \cdot h)$ ~O(n^2 \cdot h)~

Ovo rešenje dobijamo jednostavnim simuliranjem protokoa. Naime, za svako $i = 1 \ldots n$ ~i = 1 \ldots n~ "pustimo" jedinični protok sa vrha vodopada $i$ ~i~-te kolone i simuliramo ponašanje tog jediničnog protoka. Kad protok udari u stenu, tada ga preusmeravamo levo ili desno prateći pravila opisana u postavci zadatka. Kada protok završi na dnu vodopada u koloni $j$ ~j~ tada uvećamo za $1$ ~1~ ispis za kolonu $j$ ~j~.

Da bismo protok koji udari u stenu pravilno podelili levo i desno, primetimo prvo da postavku problema možemo preformulisati na sledeći način. Posmatrajmo blok stena $B$ ~B~.

Ako je $B$ ~B~ u neparnom redu, tada se neparni po redu protok koji udari u $B$ ~B~ preusmerava levo, dok se parni po redu protok koji udari u $B$ ~B~ preusmerava desno.
Ako je $B$ ~B~ u parnom redu, tada se neparni po redu protok koji udari u $B$ ~B~ preusmerava desno, dok se parni po redu protok koji udari u $B$ ~B~ preusmerava levo.

Dakle, za simulaciju je dovoljno da za svaki blok stena pamtimo gde smo \emph{poslednji} put preusmerili protok sa tog bloka.

U ovom rešenju imamo $n$ ~n~ jediničnih protoka koje simuliramo "polje po polje". Pošto blok stena može imati dužinu $n - 1$ ~n - 1~, dati protok može obići $O(n \cdot h)$ ~O(n \cdot h)~ polja pre nego što dođe do dna. Odatle sledi gore naznačeno vreme izvršavanja.

Rešenje u $O(n \cdot h)$ ~O(n \cdot h)~

Da bismo ubrzali opisano rešenje iznad, dovoljno je da za svaki blok stena zapamtimo gde su kraj i početak bloka. Tada kada protok udari bilo gde u blok možemo ga odmah simulirati sa jednog od krajeva bloka, bez potrebe da protok polje po polje prelazi preko celog bloka stena. To znači da se svaki red može simulirati u $O(1)$ ~O(1)~ vremenu, što daje ukupnu složenost od $O(n \cdot h)$ ~O(n \cdot h)~.

Smernice za algoritam

Za algoritam je potrebno da označimo kom bloku svaka stena pripada, kao i da za svaki blok odredimo njegov početak i kraj. Da bismo to uradili, najpre ćemo svakom bloku uzastopnih stena dodeliti jedinstven broj, na primer, redom brojeve počevši od $1$ ~1~. To možemo uraditi na sledeći način. Čuvaćemo promenljivu $blockNumber$ ~blockNumber~, koja će označavati redni broj trenutnog bloka, i obilaziti polja redom po redovima. Kada naiđemo na stenu, ona je početak novog bloka ako i samo ako je ta stena prva u tom redu, ili ako je prethodno polje bilo $1$ ~1~. Kada detektujemo početak bloka, tada uvećamo $blockNumber$ ~blockNumber~ za $1$ ~1~. Steni, bila prva u bloku ili ne, dodelimo $blockNumber$ ~blockNumber~.

Posle ovih koraka svakoj steni je dodeljen broj koji označava kom bloku ona pripada. Stena bloka sa najmanjom kolonom označava početak odgovarajućeg bloka, a stena bloka sa najvećom kolonom označava kraj odgovarajućeg bloka.

Bonus zadatak

Simulacija koja donosi 100 poena ključno zavisi od činjenice da postoji $n$ ~n~ jediničnih protoka. Kako bi se mogao ovaj zadatak rešiti u $O(n \cdot h)$ ~O(n \cdot h)~ vremenu ako se sa vrha vodopada iz $i$ ~i~-te kolone pušta između $0$ ~0~ i $10^9$ ~10^9~ zapremine vode?

Comments

There are no comments at the moment.