Solutii Algoritmiada 2009, Runda 1

Tablete

Pe baza a catorva observatii, se poate gasi o multitudine de reguli de completare a matricii N x N, tinand cont de restrictiile din enunt. Iata o solutie posibila, cu mentiunea ca nu e singura:

  • Daca K este par, se completeaza dreptunghiul N x K (partea din stanga a matricii) in ordine, de la stanga la dreapta si de sus in jos, cu numerele de la 1 la N x K.
  • Daca K este impar, iar N par, se iau iarasi numerele in ordine crescatoare si se completeaza dreptunghiul N x K (partea din stanga) pe fasii de 2 x K in felul urmator:
12...K - 1K + 1
KK + 2...2 * K - 12 * K
  • Daca K este impar, iar N este tot impar, se completeaza ca mai sus pe fasii, cu mentiunea ca ultima fasie va fi completata pe jumatate, iar ultima linie din dreptunghiul N x K va contine numerele (N - 1) * K + 1, (N - 1) * K + 2, ..., N * K - 1, N * K + 1. Valoarea N * K o putem pune in pozitia (1, K + 1).

In toate situatiile de mai sus, partea din dreapta a matricii ramasa necompletata se completeaza de la stanga la dreapta si de sus in jos cu numerele ramase. Astfel, toate restrictiile din enunt sunt satisfacute.

Densitate

Problema cere sa raspundeti la intrebari de forma: "Cate numere prime sunt intre a si b?" (a si b inclusiv), cu 0 < a ≤ b ≤ N < 500000. Complexitatea dorita pentru preprocesare este O(N log logN) si cea pentru query este de O(1).
In primul rand trebuie sa stim care sunt numele prime intre 1 si N. Algoritmul clasic de verificare a divizibilitatii unui numar x cu toate valorile pana la x/2 este ineficient, avand complexitate O(x), acesta poate fi optimizat pana la O(sqrt(x)) daca se verifica numai numerele intre 2 si sqrt(x), dar acesta este eficient doar daca se testeaza primalitatea unui singur numar. Noi insa dorim sa stim toate numrele prime intre 1 si N si pentru asta se foloseste Ciurul lui Eratostene . Acest algoritm tine un sir V in care V[i]=1 are semnificatia ca i este prim si V[i] = 0 inseamna ca i nu e prim. La pasul i, daca i este prim, se seteaza V[k] = 0 pentru toti multiplii k lui i pana la N. Complexitatea acestui algoritm este O(N/2 + N/3 + N/5 ... ) = O(N log logN)
La pasul al doilea trebuie sa raspundem la intrebari. Sa parcurgem toate valorile intre a si b ar fi ineficient. Tinem insa un sir de sume cumulate S unde S[i] reprezinta numarul de numere prime mai mici sau egale decat i, astfel S[i] = S[i-1] + V[i]. Raspunsul se calculeaza ca S[b] - S[a-1]. Metoda sumelor cumulate poate fi extinsa pentru un spatiu Nk.

Propozitie

Fie S sirul initial de caractere. Vom rezolva problema cu ajutorul programarii dinamice. Vom construi o matrice A, in care A[i][j] va reprezenta numarul de posibilitati de a obtine propozitii valide cu primele i caractere, iar ultimul cuvant din propozitie sa aibe exact j vocale. Pentru a calcula valorile A[i][j] putem proceda in urmatorul fel: alegem intai subsecventa de litere SjSj+1...Si si o vom considera pe aceasta ultimul cuvant dintr-o propozitie valida. Daca subsecventa de litere de la k la i contine p vocale atunci va trebui sa adunam la A[i][p] toate valorile A[j-1][q], unde q este cuprins intre 0 si K. Evident vom considera doar subsecventele pentru care p ≤ K. O implementare bruta a acestei solutii va avea complexitatea O(N*N*K). Putem reduce complexitatea la O(N*N) daca vom precalcula B[i] = A[i] [0] + A[i] [1] + ... + A[i] [K] . Plecand de la aceasta idee putem dezvolta o solutie de complexitate O(N*K). Vom calcula A[i][j] [0] numarul de propozitii valide formate cu primele i caractere in care ultimul cuvant are j vocale si se termina pe pozitia i si A[i][j] [1] numarul de propozitii valide cu primele i caractere in care ultimul cuvant are j vocale si nu se termina pe pozitia i. Relatiile de recurenta se obtin usor in O(1) si complexitatea va fi O(N*K) ca timp si O(K) ca memorie (observam ca sunt suficiente doar ultimele doua linii din matrice). Putem optimiza si mai mult aceasta solutie observand ca de fapt daca am calcula B[i] fiind numarul de propozitii valide continand doar primele i caractere, B[i] = B[i-1]+B[i-2]+...+B[j], unde j este cel mai mic posibil astfel incat Sj+1Sj+2..Si are cel mult K vocale. Cand suntem la pasul i vom avea un indice j, la trecerea la pasul i+1 se observa ca acest indice ori ramane la fel, ori in cazul in care Si+1 este vocala si aveam deja K vocale indicele j creste pana cand vom avea din nou cel mult K vocale. Astfel putem obtine o solutie in complexitate O(N) ca timp si de asemenea O(N) ca memorie. Oricare din aceste ultime doua solutii obtinea punctajul maxim.

Jstc

Prima observatie necesara in rezolvarea problemei este faptul ca stiva este intotdeauna crescatoare. A doua observatie este ca raspunsul pentru un anumit numar x poate doar sa creasca dupa diferite operatii de tip insert sau erase (el poate sa fie si -1 dar acesta este un caz particular usor de rezolvat).
In continuare ideea rezolvarii este una gen "multimi disjuncte". Vom tine pentru fiecare numar x care poate aparea ca query nxt[x] ce reprezinta un numar mai mare ca x dar care sigur nu sare de urmatorul numar mai mare ca x ce se afla momentan in stiva. Cum zicea a doua observatie nxt[x] poate doar sa creasca in urma diverselor operatii. Acum pentru a cauta raspunsul si anume primul numar din stiva mai mare sau egal cu x vom parcurge pe rand nxt[x], nxt[nxt[x]], nxt[nxt[nxt[x]]]... pana cand gasim un numar care se afla in stiva (putem tine un vector de char sau unul pe biti pentru a verifica daca un numar se afla in stiva sau nu rapid, sau pentru x ce se afla in stiva sa tinem nxt[x] = x). Tot conform celei de a doua observatii putem acum sa modificam valorile nxt[x], nxt[nxt[x]], nxt[nxt[nxt[x]]]... in raspunsul pentru intrebarea x. Astfel drumurile se vor "compacta" si nu vom parcurge de prea multe ori aceleasi drumuri pentru ca este inutil.
Aceasta abordare duce la o complexitate aproximativ O(1) amortizat pe intrebare, ce obtine punctajul maxim.

Alta solutie evidenta era cautarea binara dar aceasta nu ia punctaj maxim.

Coprime

Vom modela problema sub forma unui graf in care colegii Mirunei reprezinta nodurile, iar perechile de copii care au primit bomboane ce reprezinta doua numere prime intre ele muchiile. Va trebui sa atribuim fiecarui nod x o valoare N[x], astfel incat sa existe o muchie (x, y) daca si numai daca (N[x], N[y]) = 1. Initial vom atribui fiecarui nod valoarea 1. Apoi, vom considera fiecare muchie care nu apare in graf, si vom inmulti valorile capetelor sale cu un numar prim care nu a mai fost folosit anterior. La sfarsit vom afisa valorile obtinute. Este necesara folosirea numerelor mari, iar pentru a nu afisa prea multe cifre trebuie considerate cele mai mici numere prime posibile.

Scandura

Notam lungimea scandurei finale i cu l[i].

Vom incerca sa reprezentam taieturile scandurilor sub forma unui arbore. Radacina arborelui va fi scandura initiala de lungime L = \sum{l[i]}. In urma unei taieturi, dintr-o scandura de lungime A vor porni maxim M alte muchii catre noduri a caror suma a lungimilor va fi tot A. Frunzele arborelui vor reprezenta cele N lungimi de scanduri finale. Costul unei modalitati de taiere a scandurii mari va fi atunci egal cu suma valorilor nodurilor din arbore care nu sunt frunze. Datorita faptului ca un nod in arbore are costul egal cu suma costurilor fiilor, putem reprezenta costul fiecarui nod in functie de costul frunzelor. Daca drumul de la frunza i pana la radacina trece prin k noduri (incluzand radacina, neincluzand frunza), atunci costul total produs de frunza i va fi egal cu k * l[i]. Costul total al unei modalitati de taiere va fi egal cu \sum{l[i] * distanta(i, radacina)}.

Pentru M = 2, putem echivala imediat problema cu cea a determinarii unei codari Huffman. Codarea Huffman este o metoda de comprimare a datelor, cunoscandu-se pentru fiecare caracter din alfabet frecventa cu care el apare in text. Deoarece unele caractere apar mai des decat altele, putem comprima textul asociind lungimi diferite in reprezentarea binara a fiecarui caracter si deci costul total pentru a reprezenta un text va fi egal cu \sum{len[i] * frecventa[i]}, unde len[i] este lungimea reprezentarii caracterului i, iar frecventa[i] este frecventa cu care apare el. Reprezentarea huffman genereaza un arbore in acelasi mod ca si problema noastra, un bit de 0 simbolizand vecinul stang, un bit de 1 simbolizand vecinul drept. Fiecarei scanduri initiale de lungime l[i] ii putem asocia un caracter distinct cu o frecventa de l[i] si se observa ca problemele devin echivalente.

Pentru M > 2 putem extinde codarea Huffman, considerand ca un caracter este reprezentat in baza M, in loc de baza 2.

Pentru M = 2, o codare Huffman de cost minim se determina extragand la fiecare pas cele 2 noduri cu cost cel mai mic si inlocuirea lor cu un nod de cost egal cu suma lor. Acelasi lucru il vom face si pe cazul generalizat. Observam ca este optim sa taiem la fiecare pas scandura in cat mai multe bucati, doar la ultima taietura rezultand mai putin de M bucati. Pentru a ne usura implementarea vom adauga la inceput cateva scanduri auxiliare de lungime 0 pana cand fiecare scandura o vom putea taia in fix M bucati. La fiecare pas din algoritm vom scoate M noduri din structura si vom adauga unul inapoi, in final ramanand cu un singur nod cu costul egal cu suma scandurilor, deci vom adauga inainte de executarea algorimului scanduri de lungime 0 pana cand N devine de forma (M - 1) * k + 1.

Implementarea in O(N log N) a algoritmului pentru determinarea codarii Huffman, cu ajutorul structurilor de date heap, obtine 70 de puncte. Pentru 100 de puncte este necesara implementarea algoritmului in complexitate O(N), folosind faptul ca lungimile scandurilor in fisierul de intrare sunt sortate.

Piese2

Vom imparti cele 2*K piese in K perechi: prima piesa rosie va fi in pereche cu prima piesa albastra, a doua piesa rosie cu a doua piesa albastra, samd. Observam ca jucatorul care va duce piesele intr-o configuratie in care piesele din aceeasi pereche sunt adiacente, pierde. De aici vine ideea calcularii paritatii sumei numarului de pozitii libere intre piesele din fiecare pereche. Daca aceasta suma este impara, atunci va castiga Miruna, iar strategia pe care o va urma va fi sa mute la fiecare pas o piesa catre dreapta. Daca suma este para, va castiga Aglaia iar strategia ei este sa mute la fiecare pas o piesa catre stanga.

Sprim

Fie A[i] vectorul citit. Consideram pentru fiecare pozitie i vectorul P[i] pozitia cea mai din dreapta pana in pozitia i, astfel incat A[i] nu e prim cu A[P[i]]. Vrem sa calculam S[i] = pozitia unde incepe subsecventa maximala (ce respecta conditiile din enunt) care contine i pe ultima pozitie. Raspunsul este suma tuturor i - S[i] cu 1 ≤ i ≤ N.
Presupunem ca avem calculat S[i-1] si vrem sa calculam S[i]. Se observa doua conditii necesare si suficiente pentru S[i]:

  1. S[i] > P[i] (e clar ca subsecventa care contine i nu poate sa treaca sau sa contina P[i] pentru ca astfel nu se respecta conditia)
  2. S[i] ≥ S[i-1] (trebuie ca subsecventa care contine i sa nu treaca mai departe de subsecventa care contine i-1 pentru ca iar nu se respecta conditia)

De aici rezulta ca S[i] = max(S[i-1], P[i] + 1). Tot ce ramane de calculat este P[i] si dupa aceea S[i] se poate calcula secvential de la 1 la N.

Pentru a calcula P[i] eficient vom proceda in felul urmator: ca sa stim cea mai din dreapta pozitie pana in i astfel incat A[i] nu e prim cu A[P[i]] ne intereseaza cel mai din dreapta numar care contine un factor prim al lui A[i]. Aceasta este usor de facut tinand un vector cu ultima aparitie al fiecarui factor prim pana la pozitia i. P[i] va fi maximul dintre ultimele pozitii ale factorilor primi ai numarului A[i]. Dupa ce terminam de procesat numarul A[i] modificam vectorul cu aparitiile factorilor primi ai lui A[i] cu pozitia i.

Aveti grija la descompunerea numerelor in factori primi. Pentru a lua punctaj maxim se recomanda incercarea secventiala a fiecarui numar prim pana in sqrt(A[i]).

Kprime

Vom verifica pentru fiecare numar din sir daca este prim sau nu, iar apoi ne vom construi un sir S, pentru care S[i] va reprezenta numarul de elemente prime care se afla intre pozitiile 1 si i. Apoi pentru fiecare pozitie, vom incerca sa determinam numarul de subsecvente care contin K numere prime si au capatul din dreapta pe pozitia aleasa. Pentru o pozitie i, va trebui sa determinam cel mai mic j1 pentru care S[i] - S[j1] = K si cel mai mare j2 pentru care S[i] - S[j2] = K. Pentru a obtine punctaj maxim, era suficienta folosirea cautarii binare, desi se poate obtine o complexitate O(N) a acestui pas plimbandu-ne cu trei pointeri.