Problema A

Este evident ca produsul maxim ar fi obtinut prin inmultirea celor mai mari trei numere din sir. Fie M1, M2, M3 cele mai mari 3 numere din sir, iar P1, P2, P3 pozitiile pe care se afla acestea. Pentru simplitatea explicatiei, vom trata cazul in care P1 < P2 < P3. Pentru acest caz, vom alege subsecventele: [1, P1], [P1 + 1, P2], [P2 + 1, P3]. Cum maximul din prima subsecventa este M1, maximul din cea de-a doua subsecventa este M2, iar maximul din a treia subsecventa este M3, produsul maxim a fost obtinut, si anume M1 * M2 * M3. Celelalte cazuri se trateaza analog.

Problema cu becuri

Construim un graf cu N + 1 noduri in care fiecare nod reprezinta o stare. Starea initiala este reprezentata de nodul 1. Fiecare nod i > 1 va reprezenta starea in care sunt aprinse doar becurile [1,i-1].

Pentru fiecare comutator care schimba becurile din intervalul [a,b] adaugam o muchie intre nodurile a si b+1. Explicatia este: a reprezinta becurile aprinse in intervalul [1,a-1] la care se adauga cele din intervalul [a,b] si rezulta [1,b], adica nodul b+1.

Deci, putem aprinde becurile [1,X-1] daca exista un drum de la nodul 1 la nodul X. Raspunsul la problema va fi distanta minima a unui astfel de drum, ceea ce putem afla cu o parcurgere in latime (deoarece toate muchiile au costul 1).

Solutia are complexitatea O(N + M).

Raci

Avand un sir de N cuvinte trebuie sa aflam un subsir care sa respecte proprietatile din enunt.
O prima solutie foloseste programarea dinamica si este asemanatoare celei de la aflarea celui mai lung subsir crescator, difera doar conditia de potrivire a sirurilor.

Ne definim o stare dp[i] = cel mai lung subsir care respecta conditiile si se termina in cuvantul i. Cand calculam dp[i], incercam sa gasim un cuvant j < i, j >= i - K astfel incat ultima litera din cuvantul j este egala cu prima litera din cuvantul i.
Valoarea lui dp[i] va fi maximul dintre toate dp[j] care respecta conditia, la care adaugam 1.

Din pacate, o astfel de solutie are complexitatea O(N * K), ceea ce depaseste cu mult limita de timp.

Putem imbunatati acest algoritm. Notam prima litera a cuvantului i cu p. Observam ca atunci cand potrivim sirurile, cautam doar cuvintele care se termina cu litera p. O idee ar fi sa creem o lista de indici pentru fiecare litera. Notam lista pentru litera p cu L[p]. Vom cauta in L[p] indicii j >= i - K si luam maximul dintre aceste valori. Putem considera aceste liste ca fiind cozi cu doua capete si putem actualiza maximul din toate cele 26 cozi pe masura ce adaugam indicii (vezi descriere deque). Actualizarile au complexitatea O(N) amortizat.

Acum solutia are complexitatea optima O(N).

Suma5

Problema este o aplicatie clasica a arborilor de intervale cu lazy propagation. Fiecare nod al arborelui de intervale va retine informatii legate de:

  • Capatul stang al intervalului (st)
  • Capatul drept al intervalului (dr)
  • Suma elementelor din interval (s1)
  • Raspunsul la un query fix pe acel interval (s2)

Acum singura problema care ne mai ramane este unirea a doua noduri a si b intr-un singur nod c (altfel spus, unirea a doua jumatati de interval intr-un singur interval, mentinand toate informatiile de mai sus). Informatiile legate de capetele noului interval sunt usor de calculat dupa urmatoarele formule intuitive:

c.st = a.st;
c.dr = b.dr;

Calcularea sumei noului interval se obtine prin adunarea sumelor intervalelor a si b.

c.s1 = a.s1 + b.s1;

Calcularea noului s2 este putin mai complexa:

c.s2 = a.s2 + (b.s2 + b.s1 * (a.dr - a.st + 1));

Problema a fost aleasa drept cea mai grea problema a setului pentru ca rezolvarea presupunea cunoasterea si aplicarea teoriei, dar si o atentie sporita intr-o implementare laborioasa.