Okruzno 2017, 3 zadatak, B kategorija?

Moze li neko da mi ukratko objasni na koju foru se radi ovaj zadatak?
Hvala :smiley:

Link od teksta: http://takprog.petlja.org/resources/Okruzno2017_zadaci.pdf

Ukratko hintovi:

Da bi razlika bila najveća moguća, potrebno je u nekom izabranom podnizu da se nalazi bar jedan marsovac koji je najviši od svih, i bar jedan koji je najniži. Primetimo i da ako podniz od L do R zadovoljava taj uslov, onda i svi podnizovi od L’ do R (gde je L’ < L) takodje zadovoljavaju. To nam pomaže da ako fiksiramo R, treba da nadjemo samo najveće moguće L za koje je podniz dobar, i to najveće L će biti neki marsovac koji je ili najveći ili najmanji (u suprotnom možemo da povećavamo L dok ne dodjemo do nekog takvog)… Sada treba da razmisliš o tome kako brzo možeš da nadjes najveće L za svaku moguću vrednost R.

Kaži ako i dalje ne uspevaš da skontaš, ali u svakom slučaju ćemo uskoro okačiti rešenja zadataka sa svih takmičenja od ove godine. :slight_smile:

1 Like

Hvala, uspeo sam da ga resim :smiley: