Solutii Algoritmiada 2018 Runda Finala

Solutia problemei Balbaiala

Multumim lui MatteoalexandruMatteo Verzotti Matteoalexandru pentru editorial!

Sa notam cu M marimea inputului.

Putem observa ca daca balbaiala de ordin x a sirului B apartine ca subsir in sirul A, atunci orice balbaiala a acestuia de ordin y va apartine ca subsir in sirul A, unde 0 ≤ y ≤ x. Asta inseamna ca exista un x astfel incat toate balbaielile de ordin mai mic sau egal cu x apar ca subsir, dar balbaiala de ordin x + 1 nu apare ca subsir. Deci putem cauta binar aceasta valoare.

Pentru 20 de puncte

Pentru 20 de puncte, putem construi de mana sirul de balbaiala x al sirului B si sa verificam in O(N) daca acesta apartine ca subsir.

Pentru 40 de puncte

Pentru 40 de puncte, aceasta solutie trebuie optimizata la verificarea proprietatii de subsir. Putem sa precalculam matricea nextpos[let][pos], care ne va spune pozitia minima > pos pe care apare litera let in sirul A. Spre exemplu, daca ma aflu pe pozitia pos in sirul A, pe care se afla litera A[pos], atunci cea mai din stanga pozitie > pos pe care se afla litera A[pos + 1] va fi exact nextpos[A[pos + 1]][pos]. In concluzie, putem lua fiecare litera din balbaiala de ordin x a sirului A si verifica daca pozitia pe care o cautam nu depaseste finalul sirului. Daca aceasta conditie este adevarata, sarim la pozitia dorita, schimbam litera si continuam. Daca nu, returnam fals. Aceasta solutie are complexitate de O(|B| * x) pentru fiecare x.

Aceasta solutie trebuie optimizata putin mai mult. Cum putem face asta? Folosind matricea calculata anterior noi putem sari din aparitie in aparitie a unei litere. Insa putem chiar mai bine - sa sarim din x in x aparitii!

Pentru 70-100 de puncte

Pentru 70 de puncte, vom grupa literele in 26 de "bucket-uri". In bucket-ul unei litere vom retine toate aparitiile acesteia in sirul A, in ordine crescatoare. Asta ne poate ajuta sa sarim de la o aparitie a unei litere la oricare alta. Vom retine o variabila pos, care ne va spune pozitia de dupa ultima litera luata. Cu alte cuvinte, pos ne va spune la fiecare moment de timp prefixul minim al lui A de care avem nevoie pentru ca prefixul deja procesat al lui B sa fie subsir in A. La inceput, pos va fi egal cu 0. Pentru fiecare litera din B vom cauta binar in bucket-ul corespunzator prima aparitie a ei de dupa pos, dupa care vom sari peste x aparitii ale acesteia si vom actualiza valoarea lui pos. Aceasta solutie are o complexitate teoretica de O(M * log2M), insa in practica, cu mici optimizari poate obtine 100 de puncte. Un avantaj al acestei solutii este memoria ocupata, noi nemaiavand nevoie de matricea nextpos.

Pentru 100 de puncte

In loc sa cautam binar in bucket-ul unei litere prima ei aparitie de dupa pos, putem sa precalculam pentru fiecare litera pe ce pozitie se afla in bucket-ul care o contine. Dupa ce trecem de la litera B[k] la litera B[k+1], actualizam valoarea lui pos. Apoi, folosindu-ne de matricea nextpos, calculata anterior, putem sa aflam prima pozitie a literei B[k + 1] de dupa pos, adica nextpos[B[k + 1]][pos]. Acum, stiind pozitia pe care se afla litera aceasta in bucket-ul ei, ne vom duce pe aceasta pozitie in bucket, vom lua urmatoarele x litere si vom actualiza valoarea lui pos. Aceasta solutie reduce complexitatea la O(M * logM), care intra lejer in restrictiile problemei.

Solutia problemei Valoare

Multumim lui MatteoalexandruMatteo Verzotti Matteoalexandru pentru editorial!

Vom folosi un rationament inductiv. Notam cu f(k) cea mai mare suma care poate fi atinsa (si toate mai mici decat ea) folosind k monede.

  • Pasul I: f(1) este 1 daca exista elementul 1 in vectorul dat, altfel este 0;
  • Pasul II: Stim f(k) si vrem sa aflam f(k + 1). Presupunem ca f(k) = s, adica putem obtine toate sumele 1, 2, ..., s folosind k monede. Ce sume putem obtine cu k + 1 monede?

Sa presupunem ca alegem o moneda cu valoare v. Atunci noi vom putea plati toate sumele 1, 2, ..., s, v, 1 + v, 2 + v, ..., s + v. Stim ca prima jumatate a sirului este consecutiva, la fel si a doua. Deci ne ramane doar sa ne asiguram ca nu exista "gauri" intre s si v, adica s + 1 < v. In concluzie, la fiecare pas trebuie sa luam moneda cu cea mai mare valoare v, astfel incat v ≤ s + 1, dupa care s creste cu v. Putem obtine aceasta valoare fara sa ne chinuim prea mult, in O(logN) folosind un arbore echilibrat, sau un container STL precum multiset, aducand solutia finala la una de complexitate O(N * logN).

O alta solutie incepe cu sortarea vectorului dat. Chiar daca complexitatea finala nu poate fi redusa, din cauza acestei sortari initiale*, solutia este liniara (dupa sortare). O voi prezenta cu scop didactic:

Vom retine o stiva (la inceput goala), in care vom adauga pe parcurs valorile din vectorul initial. Sa presupunem ca ne aflam, din nou, la pasul k + 1 si vrem sa aflam valoarea v potrivita. Vom adauga in stiva noastra toate valorile mai mici sau egale cu s + 1. Observatie: Deoarece s creste la fiecare pas, este suficient sa adaugam fiecare valoare o singura data in stiva. La final, rezultatul nostru va fi, de fapt, varful stivei, pe care il scoatem. Cum vectorul este sortat crescator, iar noi adaugam elemente in stiva de la stanga la dreapta, ea va ramane mereu crescatoare. Cum fiecare element este adaugat si eliminat o singura data, pasul acesta este de complexitate amortizata liniara. Complexitatea totala a algoritmului va fi cea data de algoritmul de sortare.

*Presupunem folosirea unei metode de sortare precum QuickSort sau MergeSort. Cititorul poate, desigur, sa foloseasca si metode mai eficiente precum Radix Sort, dar nu acesta este scopul editorialului :).