h1. 'Super Mario':problema/supermario

*Solutia 1*
 
Definim o functie <tex>f(st, dr)</tex> care returneaza numarul minim de mutari necesare pentru a distruge toate testoasele din intervalul <tex>[st, dr]</tex>, folosind numai testoase din acest interval. Raspunsul va fi dat de <tex>f(1, N)</tex>.
In continuare, incercam sa gasim raspunsul pentru intervalul <tex>[st, dr]</tex>. Pe care testoasa o distrugem prima si in ce directie o impingem?
Fie <tex>p</tex> pozitia testoasei din acest interval cu puterea maxima. Observam ca la prima mutare o vom alege tot timpul pe aceasta. Nu are rost sa incepem cu alta testoasa, deoarece avem sansa sa ne lovim de tesoasa <tex>p</tex> si in acest caz era mai bine sa inversam ordinea mutarilor.
Deci, distrugem testoasa <tex>p</tex> si incercam sa o impingem in ambele directii. Daca o impingem spre stanga, distrugem toate testoasele din intervalul <tex>[st, p-1]</tex>. In acest caz avem nevoie de <tex>1 + f(p+1, N)</tex> mutari. Similar, daca o impingem spre dreapta, avem nevoie de <tex>1 + f(st, p-1)</tex> mutari. Deci, <tex>f(st, dr) = min(1 + f(st, p-1), 1 + f(p+1, dr))</tex>. Cazul de baza este <tex>st > dr</tex>.
Aceasta solutie are complexitatea <tex>O(NlogN)</tex>, deoarece in cel mai rau caz vizitam <tex>N</tex> intervale si pentru fiecare aflam maximul in <tex>O(logN)</tex>. Maximul se poate afla cu 'arbori de intervale':problema/arbint sau cu 'range minimum query':problema/rmq.
 

h1. "Hero's Call: Northrend!":problema/northrend
h1. 'Temple':problema/temple