monthly-2014/runda-8/solutii

Infoarena Monthly 2014 - Runda 8, Solutii

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.

*Solutia 2*
 
Aceasta solutie se bazeaza pe programare dinamica. Precalculam doi vectori $left$ si $right$ cu semnificatia $left[i]$ = testoasa cea mai din dreapta care se afla in stanga testoasei $i$ si are puterea mai mare ca aceasta. Formal, $left[i] = max(j | j < i si P[j] > P[i])$. Similar, $right[i] = min(j | j > i si P[j] > P[i])$.
Definim starea ca si $dp[i]$ = numarul minim de mutari necesare pentru a distruge primele $i$ testoase. Pentru fiecare testoasa $i$ pe care o distrugem avem doua variante:
 
* O impingem spre stanga. Distrugem toate testoasele din intervalul $[left[i]+1, i]$, deci $dp[i+1] = min(dp[i+1], 1 + dp[ left[i]+1 ])$.
* O impingem spre dreapta. Distrugem toate testoasele din intervalul $[i, right[i]-1]$, deci $dp[ right[i] ] = min(dp[ right[i] ], 1 + dp[i])$.
 
Raspunsul se afla in $dp[N]$.
Vectorii $left$ si $right$ se pot precalcula cu ajutorul unei stive in $O(N)$. Complexitatea finala a acestei solutii este $O(N)$.
 

h1. "Hero's Call: Northrend!":problema/northrend
In continuare, vom considera fiecare oras din cele $N$ ca fiind un nod, iar fiecare portal ca fiind o muchie care conecteaza doua noduri, in schimbul unui cost. Asadar, este destul de evident ca structura noastra este un arbore cu $N$ noduri.