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), š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) i donese 100 poena.

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

Ovo rešenje dobijamo jednostavnim simuliranjem protokoa. Naime, za svako i = 1 \ldots n "pustimo" jedinični protok sa vrha vodopada 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 tada uvećamo za 1 ispis za kolonu 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.

  • Ako je B u neparnom redu, tada se neparni po redu protok koji udari u B preusmerava levo, dok se parni po redu protok koji udari u B preusmerava desno.
  • Ako je B u parnom redu, tada se neparni po redu protok koji udari u B preusmerava desno, dok se parni po redu protok koji udari u 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 jediničnih protoka koje simuliramo "polje po polje". Pošto blok stena može imati dužinu n - 1, dati protok može obići 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)

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) vremenu, što daje ukupnu složenost od 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. To možemo uraditi na sledeći način. Čuvaćemo promenljivu 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. Kada detektujemo početak bloka, tada uvećamo blockNumber za 1. Steni, bila prva u bloku ili ne, dodelimo 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 jediničnih protoka. Kako bi se mogao ovaj zadatak rešiti u O(n \cdot h) vremenu ako se sa vrha vodopada iz i-te kolone pušta između 0 i 10^9 zapremine vode?


Comments

There are no comments at the moment.