==Include(page="template/monthly-2014")==
h1. 'Training Dummy':problema/dummy
Avand o secure cu puterea <tex>P</tex> si o papusa cu <tex>X</tex> puncte de viata, avem nevoie de <tex>\lceil\frac{X}{P}\rceil</tex> lovituri pentru a distruge papusa. Deci, numarul mediu de secunde este egal cu <tex>\sum\limits_{i=A}^{B}P(\text{securea echipata are puterea i})\cdot\lceil\frac{X}{i}\rceil = \sum\limits_{i=A}^{B}\frac{1}{B-A+1}\cdot\lceil\frac{X}{i}\rceil = \frac{1}{B-A+1} \sum\limits_{i=A}^{B}\lceil\frac{X}{i}\rceil</tex>.
Solutia are complexitatea <tex>O(T(B-A))</tex>.
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.
*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.
Vom construi toate drumurile posibile "invers", folosind o parcurgere in adancime din nodul $X$. Vom parcurge toate nodurile vecine cu nodul $X$. Avem doua cazuri:
* Muchia $(Y, X)$ are cel mai mic cost dintre muchiile conectate de nodul $Y$. Deci, in nodul $Y$ am fi putut ajunge prin oricare alt nod conectat de el, in afara de $X$.
* Muchia $(Y, X)$ este a doua in sirul muchiilor sortate crescator dupa cost, conectate de nodul $Y$. Deci, este evident ca in nodul $Y$ am ajuns prin muchia minima din acest nod.
* Altfel,
h1. 'Temple':problema/temple
Construim un arbore in care tatal nodului $x$ este $Next[x]$. Astfel, observam ca $S[x]$ este, de fapt, maximul din valorile primilor $K$ stramosi ai lui $x$. Pentru a calcula aceste valori, putem face o parcurgere DFS, sa retinem nodurile de pe lantul curent intr-o stiva si sa mentinem o structura de date (multiset, arbore de intervale etc.) cu valorile ultimelor $K$ noduri de pe lant.
Complexitatea de timp este $O(N * logN)$, iar memoria folosita este $O(N)$.
==include(page="template/monthly-2014/footer")==
