Soluţii Grigore Moisil 2009

Alibaba

Vom prezenta trei moduri de abordare a rezolvării.

Varianta 1 (propusă de Clara Ionescu)

Să observăm că la fiecare pas trebuie tăiată ultima cifră dintr-o secvenţă descrescătoare de cifre aflate pe poziţii consecutive. Astfel peste această cifră vom putea pune cea aflată pe poziţia imediat următoare şi care are valoare mai mare. Conform acestui algoritm pentru exemplul din enunţ (12312) se vor obţine pe rând numerele: 2312, 312, 32.

Algoritmul de mai sus pierde timp preţios efectuând translatările aferente tăierii unei cifre. În concluzie vom crea un şir martor în care memorăm faptul că o anumită cifră este tăiată sau nu.

Varianta 2 (propusă de Pătcaş Csaba)

Pornim de la observaţia că pentru a maximiza numărul trebuie să aducem pe prima poziţie cea mai mare cifră posibilă. Dacă putem tăia maxim k cifre, rezultă că vom putea muta pe prima poziţie o cifră dintre primele k + 1 cifre. Pornim cu cifrele din intervalul [1, n] şi cu valoarea k. Dacă cifra având valoare maximă din intervalul [1, k + 1] se află pe poziţia l, atunci problema se reduce la intervalul [l + 1, n] şi valoarea k – l. O implementare naivă va avea complexitatea O(k2) în cel mai rău caz, dar în practică algoritmul se comportă mult mai bine. Menţionăm că complexitatea se poate reduce la O(k log k) folosind arbori de intervale.

Varianta 3 (propusă de Marius Stroe)

Soluţia foloseşte metoda greedy. În continuare, vom considera S ca fiind şirul cifrelor. Pentru a forma cel mai mare număr, trebuie ca pe primele poziţii să avem cifre cât mai mari. Din acest motiv, vom căuta prima cea mai mare cifră din şir, după care următoarea cea mai mare cifră din şir ş.a.m.d. Spre exemplu, pentru şirul 1295413746 cifrele găsite sunt, în această ordine, 9, 7 şi 6. Cu aceste cifre vom forma un număr T, aici 976, care este cel mai mare dacă, în cazul acesta, trebuie să eliminăm 7 cifre. Dacă, însă, numărul cifrelor ce trebuie eliminate este mai mic, atunci trebuie să avem un şir T mai lung adăugându-i noi cifre din cele rămase. Când vom insera aceste cifre noi, vrem ca cele găsite până acum să rămână pe poziţii cât mai înaintate. De aceea, pentru fiecare şir rămas cuprins între cifrele găsite, 12, 5413, 4, vom aplica acelaşi procedeu, însă, le vom considera în ordine inversă, 4, 5413, 12, pentru ca cifrele cele mai mari să rămână pe poziţii cât mai semnificative. Vom repeta recursiv procedeul până când şirul T are lungimea n – k.

Subproblema determinării celei mai mari cifre, a următoarei celei mai mari cifre ş.a.m.d. se rezolvă cu ajutorul unei stive în timp liniar. Algoritmul parcurge şirul cifrelor de la cea mai semnificativă la cea mai puţin semnificativă, scoate din stivă toate elementele care sunt mai mici strict decât cifra curentă, iar apoi o inserează pe aceasta în vârful structurii de date.

...
stk_len = 0
pentru i = 1, n execută
  cât timp (stk_len > 0) şi (stk[stk_len] < stk[i]) execută
    stk_len --;
  sfârşit cât timp
  stk[stk_len] = S[i]
  stk_len ++
sfârşit pentru
...

Complexitate finală: O(n)

Palindrom2

Se aplică metoda Greedy. Conform cerinţei din enunţ se impune să inserăm caractere doar la sfârşitul şirului. Observăm că un palindrom de lungime minimă se obţine prin inserarea unui număr minim de caractere la sfârşitul şirului. Pentru a obţine acest număr minim trebuie să găsim lungimea maximă a unui palindrom care se termină pe ultima poziţie a şirului.

Spre exemplu, dacă şirul iniţial este abcdzyxyz, palindromul căutat este zyxyz, iar rezultatul va fi abcdzyxyzdcba, adică vom adăuga caracterele aflate în faţa palindromului cu care se termină şirul iniţial, dar în ordine inversă. De aici, problema se rezumă la a determina această lungime maximă a unui palindrom care se termină pe ultima poziţie a şirului. Se fixează un indice k succesiv pe poziţiile 1, 2, ..., n şi se verifică dacă şirul S[k..n] este un palindrom:

Algoritm Pali(k, n, S, ok):
  i = k
  j = n
  ok = adevărat
  cât timp i < j şi ok execută
    dacă S[i] != S[j] atunci
      ok = fals
    sfârşit dacă
    i = i + 1
    j = j - 1
  sfârşit cât timp
Sfârşit algoritm.

Dacă ok este adevărat, atunci S[k..n] este palindrom. Algoritmul se opreşte la primul palindrom determinat, acesta fiind de lungimea cea mai mare.
Complexitate: O(n2).

Bete2

Problema revine la numărarea tripleţilor de forma a = b + c în mulţimea numerelor date şi poate fi abordată în mai multe feluri. Vom prezenta câteva posibilităţi,

Varianta 1

Cea mai simplă rezolvare se bazează pe trei for-uri. Înaintea aplicării algoritmului de mai jos, şirul se sortează descrescător.

Algoritm Bete(n, lung, nr):
  Ordonare(n, lung)	{ ordonăm şirul lungimilor în ordine crescătoare }
  nr = 0
  Pentru i = 1, n - 2 execută
    Pentru j = i + 1, n - 1 execută
      Pentru k = j + 1, n execută
        Dacă lung[i] = lung[j] + lung[k] atunci
          nr ++	       { în nr numărăm posibilităţile de a forma tripleţii de forma a = b + c }
        sfârşit dacă
      sfârşit pentru
    sfârşit pentru
  sfârşit pentru
Sfârşit algoritm

Cu această rezolvare se puteau obţine 40-50 puncte.

Varianta 2

Există şi posibilitatea generării tuturor submulţimilor având trei elemente care se acceptă pentru a fi numărate doar dacă au proprietatea cerută. Înainte de aplicarea algoritmului de mai jos, şirul se sortează descrescător.

Algoritm Generare(i):
  Pentru j = x[i - 1] + 1, n - 3 + i execută	{ şirul x are şi elementul x0 = 0, generăm mulţimi având 3 elemente }
    x[i] = j
    Dacă i < 3 atunci
      Generare(i + 1)
    altfel
      Dacă lung[x[1]] = lung[x[2]] + lung[x[3]] atunci
         nr ++
      sfârşit dacă
    sfârşit dacă
  sfârşit pentru
Sfârşit algoritm

Cu această rezolvare se putea obţine aproximativ acelaşi punctaj ca soluţia precedentă.

Varianta 3

Îmbunătăţim varianta 1 reducându-i complexitatea de la Θ(n3) la Θ(n2 log n). Acest lucru este posibil înlocuind al treilea for cu algoritmul căutării binare. Cu această rezolvare se puteau obţine 100 puncte.

Varianta 4

Algoritmul poate fi îmbunătăţit în continuare prin înlocuirea căutării binare cu tabele de dispersie, obţinându-se un algoritm cu ordinul de execuţie O(n2) care ar obţine tot 100 de puncte.

Fotbal

Problema este mai dificilă decât pare la prima vedere. Întâi vom calcula numărul de puncte obţinute de fiecare echipă, numărul total de goluri înscrise şi primite şi golaverajul. Vom sorta echipele după aceste criterii şi în continuare lucrăm cu acest clasament. Vom grupa echipe de pe poziţii consecutive dacă au obţinut acelaşi număr de puncte şi vom avea trei cazuri în funcţie de mărimea unei asemenea grupe:

  1. Dacă grupa are un singur element, echipa respectivă ocupă clar locul din clasament.
  2. Dacă grupa are două elemente, trebuie verificat meciul direct dintre cele două echipe. Dacă au jucat meci egal, se va verifica golaverajul, în caz de egalitate numărul golurilor înscrise, iar dacă şi acesta este egal se va da cu banul.
  3. Dacă grupa are trei sau patru elemente, vom apela recursiv procedura, numai pentru echipele respective. Limita pentru n garantează că în cel mai rău caz se va întâmpla un singur apel de acest gen.

Un caz special, care mai trebuie tratat este, când există o singură grupă, adică toate echipele au punctaj egal. Acest caz se tratează printr-o nouă grupare, de data asta după golaveraj şi atribuirea poziţiilor corespunzătoare pentru echipele din fiecare grupă.

Complexitatea finală este O(n2).

O altă soluţie foloseşte un vector în care se reţine pentru fiecare echipă numărul echipelor mai bune decât aceasta. Întâi, vom face clasamentul după punctajul obţinut. Dacă vor exista mai multe echipe la egalitate, vom marca aceste echipe într-un vector martor şi vom reface clasamentul separat pentru ele în funcţie de rezultatul direct, golaveraj şi numărul golurilor înscrise. În implementare, dacă una din aceste echipe este mai bună decât cealaltă, se va aduna încă o poziţie la valoarea curentă din vector. După acest pas, pentru a determina poziţia cea mai bună pentru fiecare dintre echipe vom număra pe câte poziţii apar valori strict mai mici. Pentru poziţia cea mai rea pe care o poate ocupă în clasament vom aduna toate valorile din vector mai mici sau egale.

Cuburi3

Vom prezenta trei soluţii, toate aplicând metoda programării dinamice, prima fiind una cu memoizare, a doua una clasică iar a treia folosind arbori indexaţi binar.

Varianta 1

Vom arăta că soluţia are structură optimă: presupunem că turnul de cuburi format din cuburile numerotate cu p1, p2, ..., pk în această ordine are înălţime maximă. Acum turnul de cuburi format din cuburile p2, ..., pk este cel mai înalt turn care îl are la bază pe p2. Dacă ar exista turn mai înalt care la bază să îl aibă tot pe p2, atunci acesta s-ar putea aşeza pe p1 şi astfel am obţine un turn mai înalt decât cel din presupunerea iniţială. Am afirmat că acel ipotetic turn mai înalt care începe cu p2 l-am aşeza pe p1, deoarece p1 nu poate să apară în acest turn care începe cu p2, ţinând cont de proprietăţile turnului.

Descompunem problema în subprobleme: pentru orice i (1 ≤ i ≤ n) trebuie să determinăm înălţimea maximă a turnului care la bază îl are pe cubul i. Fie bsti turnul de înălţime maximă ce se termină pe poziţia i.

  • bsti = max { bstj : 1 ≤ j ≤ n, i != j şi gj ≤ gi şi lj ≤ li } + li

Vom determina soluţia optimă recursiv şi vom păstra rezultatele subproblemelor, de unde le vom citi dacă în continuare va fi nevoie de ele. Şirul care memorează rezultatele subproblemelor se iniţializează cu 0, pentru a şti dacă elementul respectiv s-a calculat deja sau nu.

Algoritmul lucrează în O(n2), şi are nevoie de Θ(n) memorie.

Varianta 2

O altă soluţie având complexitatea O(n2) se poate obţine sortând cuburile descrescător după lungimea laturii şi în caz de egalitate după greutate. După sortare putem aplica metoda programării dinamice în felul următor:

  • bsti – înălţimea celui mai înalt turn ce se poate construi în aşa fel încât ultimul cub să fie cubul i.

Sortarea ne garantează că cubul i se poate aşeza doar pe cuburi având indice mai mic. Astfel recurenţa va fi:

  • bsti = max { bstj : 1 ≤ j < i şi gj ≥ gi} + li

Soluţia se va afla în elementul maxim din bst. Pentru a putea reconstrui soluţia, trebuie reţinut pentru fiecare i, acel j prin care s-a obţinut maximul pentru bsti.

Varianta 3

Folosind arbori indexaţi binar (notat în continuare cu AIB), vom obţine un algoritm de complexitate O(n log n) care necesită Θ(n) memorie. Deoarece cerinţa problemei este de a construi un subşir (g1, l1), (g2, l2), ..., (gk, lk) astfel încât g1 ≥ g2 ≥ ... ≥ gk şi l1 ≥ l2 ≥ ... ≥ lk, întâi sortăm descrescător cuburile în funcţie de lungimea laturii, iar în caz de egalitate, descrescător în funcţie de greutate.

Pentru poziţia i vom alege bstj maxim, astfel încât greutatea cubului j, j < i, să fie mai mare sau egală cu greutatea cubului i. Observăm că j < i este echivalent cu lj ≥ li, adică condiţia lungimilor laturilor este îndeplinită. Însă, noi avem nevoie doar de greutăţile mai mari sau egale decât greutatea curentă gi. Aici intervine AIB, în felul următor:

  • sortăm crescător greutăţile cuburilor, eliminăm duplicatele obţinând un vector de lungime lung;
  • căutăm în acest vector cu algoritmul căutării binare greutatea curentă gi, găsind-o pe o poziţie p;
  • interogăm AIB-ul pe intervalul [p, lung] pentru a determina max { bstj : 1 ≤ j < i şi gj ≥ gi};
  • actualizăm în AIB intervalul [1, p] cu bsti.

Operaţiile de interogare şi actualizare într-un AIB au complexitatea O(log(n)).

Motel

Problema poate fi abordată cu metoda Greedy sau cu algoritmul determinării unui cuplaj maxim. Dar soluţia cea mai eficientă se va obţine folosind heapuri.

Varianta 1

Din păcate, aplicarea metodei Greedy nu conduce la rezultate corecte. Dacă sortăm intervalele solicitate de turişti în ordine crescătoare după ziua care închide intervalul şi sortăm crescător vectorul zilelor specificate de artist, şi parcurgem în paralel cele două şiruri pentru a verifica dacă ziua precizată de artist de pe poziţia i face parte sau nu din intervalul aflat pe aceeaşi poziţie, vom greşi, deoarece pierdem soluţii pentru cazuri de forma următoare:
2
1 4
2 3
1
2
Sortarea după ultima zi din interval ne conduce la
2 3
1 4

1 nu face parte din intervalul [2, 3] şi astfel am ajunge la concluzia că nu avem soluţie, cu toate că ea există:
1 1
2 2

O astfel de rezolvare ar fi obţinut 30 de puncte.

De asemenea, nici varianta când sortăm după extremitatea stângă a intervalelor nu funcţionează corect. Să considerăm de exemplu cazul
1 4
2 3
2
4

Vom atribui intervalului [1, 4] punctul 2 şi astfel punctului 4 nu i se va mai putea atribui intervalul rămas şi iarăşi am ajunge la concluzia că nu există soluţie. Această rezolvare obţine de asemenea 30 de puncte.

Varianta 2

Pentru cei care au cunoştinţe de teoria grafurilor o primă idee ar putea fi construirea unui graf bipartit şi încercarea găsirii unui cuplaj de cardinalitate n. Acest lucru se poate face în complexitate O(n * m) sau O(sqrt(n) * m). În cel mai rău caz m poate ajunge până la n2, dar în practică acest caz este cel mai simplu, pentru că orice cuplare între intervale şi zile duce la soluţie optimă. O implementare eficientă a acestei idei poate obţine între 55 şi 70 de puncte.

Variata 3

O soluţie mult mai simplu de implementat şi care în practică are un timp de rulare asemănător este următoarea: sortăm zilele în care artistul este disponibil în ordine crescătoare. Le parcurgem în această ordine şi atribuim fiecăruia intervalul care are extremitatea din dreapta cea mai mică, dintre intervalele care o cuprind. O implementare naivă va avea complexitatea Θ(n2) şi ar obţine între 55 şi 70 de puncte

Pentru a obţine punctaj maxim vom implementa ideea de mai sus într-un mod mai eficient. Pentru acesta trebuie să cunoaştem structura de date numită min-heap. Criteriul de sortare al heap-ului va fi extremitatea dreaptă a intervalelor.

Sortăm intervalele după extremitatea stângă. La pasul i căutăm intervalul pe care să-l cuplăm cu ziua i. Introducem în heap intervalele încă neintroduse, care cuprind ziua i, după care ştergem din heap intervalele care nu mai cuprind ziua i. Dacă heap-ul devine vid, nu există soluţie, în caz contrar cuplăm ziua i cu intervalul din vârful heap-ului. Complexitate totală: O(n log n).

Palindrom

Se aplică metoda Greedy. Conform cerinţei din enunţ se impune să inserăm caractere doar la sfârşitul şirului. Observăm că un palindrom de lungime minimă se obţine prin inserarea unui număr minim de caractere la sfârşitul şirului. Pentru a obţine acest număr minim trebuie să găsim lungimea maximă a unui palindrom care se termină pe ultima poziţie a şirului. Dacă şirul iniţial este abcdzyxyz, palindromul căutat este zyxyz, iar rezultatul va fi abcdzyxyzdcba, adică vom adăuga caracterele aflate în faţa palindromului cu care se termină şirul iniţial, dar în ordine inversă.

Notăm cu T şirul S inversat. Dacă parcurgem şirul S de la stânga la dreapta, va trebui ca pentru fiecare poziţie i să determinăm cel mai lung sufix al şirului S[1..i] care este prefix al şirului T[1..n], unde n este lungimea şirului. Dacă lungimea acestui subşir este lung atunci:

  1. dacă lung = n – i, atunci am obţinut un palindrom de lungime 2 * lung cu centrul între poziţiile i şi i + 1.
  2. dacă lung = n – i + 1, atunci am obţinut un palindrom de lungime 2 * lung – 1 cu centrul în poziţia i.
  3. dacă lung < n – i, atunci nu avem un palindrom şi ignorăm această poziţie.

Pentru a determina acest subşir observăm că este nevoie să construim funcţia prefix (cunoscut din algoritmul KMP de potrivire a şirurilor) pentru şirul T şi să parcurgem ulterior şirul S pentru a determina lungimile.

Algoritmul are complexitatea O(n).

O alta soluţie care ar fi obţinut 100 de puncte este folosirea hashurilor pentru a căuta cel mai lung sufix palindrom (vezi potrivirea şirurilor pe baza algoritmului Rabin-Karp ).
Parcugând şirul de la sfarşit se reţine intr-un hash sufixul obţinut până la acel moment, iar in alt hash inversul acestui sufix. În caz că aceste 2 hashuri sunt identice se reţine poziţia curentă şi se continuă căutarea.

Soluţia se obţine adăugând in ordine inversa, la coada şirului iniţial, caracterele aflate in stanga poziţiei de început a celui mai lung sufix palindrom.

Deoarece compararea celor doua hashuri se face in O(1) algoritmul final va avea complexitatea O(n)

Peisaj

Răspunsul la subpunctul a) este echivalent cu numărul parantezărilor corecte şi se poate calcula cu formula numerelor Catalan. Totuşi, putem observa, că subpunctul a) este de fapt un caz special al subpunctului b), când K = 1.

Pentru a rezolva subpunctul b) vom aplica metoda programării dinamice. O stare va fi definită prin trei parametri:

  • Bi,j,b (i = 1, 2, ..., N; j = 0, 1, ..., N/2, b = {adevărat, fals}) – numărul de posibilităţi prin care după aşezarea a i beţişoare se poate ajunge la nivelul j, astfel încât cerinţa problemei (de a ajunge cel puţin odată la nivelul K) să fie sau nu satisfăcută.

Recurenţele vor fi:

  • Bi,j, fals = Bi-1,j-1,fals + Bi-1,j+1,fals
  • Bi,j,adevărat = Bi-1,j-1,adevărat + Bi-1,j+1,adevărat, dacă j != K
  • Bi,j,adevărat = Bi-1,j-1,fals + Bi-1,j+1,adevărat, dacă j = K

Subpunctul c) se rezolvă tot cu metoda programării dinamice. Aici vom defini o stare în modul următor:

  • Ci,j,v,u (i = 1, 2, …, N, j = 0, 1, N/2, v = 0, 1, …, K, u = {/, \} – numărul posibilităţilor prin care după aşezarea a i beţişoare se poate ajunge la nivelul j, formând v vârfuri în aşa fel încât ultimul beţişor aşezat să fie de forma u.

Recurenţele vor fi:

  • Ci,j,v,/ = Ci-1,j-1,v,/ + Ci-1,j-1,v,\
  • Ci,j,v,\ = Ci-1,j+1,v,\ + Ci-1,j+1,v-1,/

Răspunsurile finale se vor afla în Bn,0,0, Bn,0,1, respectiv Cn,0,k,\. Complexitate finală: Θ(N2 * K).

Pari

Soluţia acestei probleme se foloseşte de noţiuni elementare din teoria grafurilor. Pentru început, considerăm un graf G format din mulţimea tuturor indicilor. Muchiile se vor construi între două noduri (i, j) astfel încât resturile împărţirii la doi a celor două numere să fie diferite iar cmmdc(i, j) ≥ d. În continuare, considerăm că nodurile au două culori: alb pentru indicii care au paritate corespunzătoare şi negru pentru indicii care nu au paritatea corespunzătoare. Rezultă că dacă nodurile negre vor dispărea atunci vom găsi o soluţie. Ideea ce se conturează este ca din fiecare nod negru să parcurgem graful în lăţime sau adâncime adunând alternativ +1 şi -1 pe muchii, adică la numerele de pe poziţiile indicate de capetele muchiei, până când găsim un alt nod negru. Observăm astfel că pe acest lanţ, singurele noduri care îşi vor schimba culoarea vor fi doar nodul sursă şi nodul destinaţie.

Complexitatea finală este O(n * m), unde n e numărul de elemente ale şirului S, iar m numărul de perechi ce se pot forma.