si un cuvant un dictionar C: aaaaaaa
Numarul de aparitii ale lui C in T este 1 dar numarul de aparitii ale unui prefix al lui C in T este <tex>O(L^2^)</tex> unde L este lungimea lui C. Urmarind procedeul de mai sus putem da peste o explozie in vectorii $matches$, dimensiunea lor find de ordinul <tex>O(Nr.aparitii.cuvinte*L^2^)</tex>. Pentru a remedia acest lucru, vom mentine in fiecare nod o valoare booleana care ne spune daca urmarind pointerul _fail_ mai putem ajunge la un nod terminal. Daca aceasta valoare este false, nu mai copiem continutul vectorului _matches_ al nodului curent mai departe.

Pana acum avem complexitate <tex>O(N + Nr.cuvinte*L + Nr.aparitii.cuvinte*L)</tex>.

Pana acum avem complexitate <tex>O(N + Nr.cuvinte*L + Nr.aparitii.cuvinte*L)</tex> unde $L$ este lungimea maxima a unui cuvant.

*Subproblema 2*

* @dp[i] = costul minim de a acoperi primele i intervale.@

Parcurgem pozitiile de pe axa Ox de la stanga la dreapta. Presupunem ca stim configuratia de intervale la care suntem la pozitia i. Aceasta va fi o secventa continua de intervale - [l..r], unde l este cel mai din stanga interval iar r este cel mai din dreapta. intervalele [1..l-1] trebuiau acoperite cu pozitii mai mici decat aceasta, nu mai avem cum sa le acoperim de aici. Asadar, este necesar si suficient sa updatam @dp[k] = min (dp[k], dp[l-1] + v[i]) pentru orice l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:

Parcurgem pozitiile de pe axa Ox de la stanga la dreapta. Presupunem ca stim configuratia de intervale la care suntem la pozitia i. Aceasta va fi o secventa continua de intervale - [l..r], unde l este cel mai din stanga interval iar r este cel mai din dreapta. intervalele [1..l-1] trebuiau acoperite cu pozitii mai mici decat aceasta, nu mai avem cum sa le acoperim de aici. Asadar, este necesar si suficient sa updatam @dp[k] = min (dp[k], dp[l-1] + v[i])@ pentru orice l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:

== code(cpp) |
int get_answer (vector<pair<int,int> > intervals)

    for (int i = 0; i < intervals.size(); ++i)
    {

        bal[intervals[i].first][0].push_back(i+1);
        bal[intervals[i].second][1].push_back(i+1);

        bal[intervals[i].first][0].push_back(i+1);  //bal[i][0] - lista de intervale care incep la pozitia i
        bal[intervals[i].second][1].push_back(i+1); //bal[i][1] - lista de intervale care se termina la pozitia i

    }
    for (int i = 1; i <= intervals.size(); ++i)
        dp[i] = inf;

    dp[0] = 0;

    int not_present = 0;
    int present = 0;

}
==

Dar stati, complexitatea nu devine cumva <tex>O(Nr.aparitii^2^)</tex> ? De fapt, fiecare interval este parcurs si updatat atata timp cat el contine pozitia curenta. Intervalele sunt de lungime maxim 100 si complexitatea acestei parti este de fapt <tex>O(N + Nr.aparitii*L)</tex>.
 
Tinem sa-l felicitam pe Andrei Popa: ==User(user="andreiiiii" type="tiny")==, care a reusit sa rezolve aceasta problema specataculos in ultimul minut.

==include(page="onis-2015/solutii-runda-1/cifrul")==
==include(page="onis-2015/solutii-runda-1/invazia")==