Revizia anterioară Revizia următoare
Solutii Algoritmiada 2010, Runda 1
Iopds
Se pot obtine 30 de puncte folosind o abordare de tip backtracking, construind pe rand toate sirurile care respecta conditia din enunt.
De asemeni, 30 de puncte se obtin folosindu-ne de propritatea A = B = 0.000 si C > 0.000. Atunci relatia se transforma in C * Xi * Xi-1 > 0, pentru ca aceasta sa fie respectata atunci atat Xi cat si Xi-1 trebuie sa aiba aceiasi signatura, de unde rezulta ca subsirul va fi format fie numai din numere pozitive, fie numai din numere negative. Fie poz numarul de numere pozitive din sirul initial, atunci ele pot forma 2poz-poz-1 subsiruri. Pentru a afla subsirurile de numere negative se procedeaza asemanator.
Un program care pentru N < 12 calculeaza rezultatul folosind backtracking iar pentru A = B = 0.000 calculeaza rezultatul cu ajutorul formulei ar obtine 50 de puncte.
Solutia de 100 de puncte contruieste rezultatul folosind programarea dinamica, sa consideram D[i] = numarul de subsiruri care il au pe ultima pozitia pe Vi. Pe D il putem calcula astfel D[i] = suma(D[j] + 1) daca A * Vi2 + B * Vj2 + C * Vi * Vj > 0. Aceasta formula reiese din observatia ca daca Vi si Vj respecta conditia, atunci il putem pune pe Vi la sfarsitul oricarui subsir care se termina cu Vj. Aceasta solutia are complexitatea O(N2).
Problema poate fi rezolvata si in complexitate O(NlogN) rezolvand inegalitatea in functie de parametrul Xi si folosind o structura de date care permite calcularea sumei pe un interval si update-ul unui element in logN, ramane ca tema pentru cei interesati.
Perle2
Se observă că găsirea unei subsecvenţe [i,j] care maximizează valoarea (A[i]+A[i+1]+...+A[j]) - K*(j-i+1) este echivalentă cu găsirea unei subsecvenţe care maximizează valoarea A[i]-K+A[i+1]-K+...+A[j]-K. Această observaţie duce la ideea de a scădea K din fiecare element al vectorului iniţial şi de a căuta apoi subsecvenţa de sumă maximă. Subsecvenţa de sumă maximă (mai multe detalii aici) poate fi localizată în complexitate timp O(N), iar o soluţie ce ar fi implementat această idee ar fi obţinut 100 de puncte.
Studenti
Fie Gmax si Hmax greutatea maxima a unui student, respectiv inaltimea maxima a unui student. Distingem doua cazuri elementare de a repartiza studentii in sali. Primul caz este sa plasam atat studentul cu cea mai mare inaltime cat si studentul cu cea mai mare greutate in aceiasi sala, sa spunem ca ii plasam in sala S1. Atunci este clar ca in celelalte doua sali se va afla cate un singur student, deoarece orice student poate intra in sala S1 fara sa modifice greutatea sau intaltimea maxima din sala. Astfel complexitatea pentru acest caz este O(N2). Al doilea caz elementar este cand Gmax si Hmax se afla in sali diferite. Sa spunem ca studentul cu greutatea Gmax il vom repartiza in sala S1 iar cel cu intaltimea Hmax in sala S2. Vom lua fiecare posibilitate de a fixa inaltimea maxima din sala S1 si greutatea maxima din sala S2. Apoi iteram prin fiecare student in parte si vedem daca el poate fi repartizat in S1 sau S2 fara sa modifice greutatea maxima sau inaltimea maxima din sala respectiva. Daca nu poate fi repartizat in S1 sau S2 il repartizam in S3. Complexitatea acestui caz este O(N3).
Pitici4
Observăm că este util să ordonăm piticii în funcţie de A şi în caz de egalitate în funcţie de B pentru ca piticii cu aceleaşi informaţii să fie grupaţi. Vom folosi apoi metoda programării dinamice pentru a determina răspunsul căutat. Fie C[i] = numărul maxim de pitici a căror informaţii nu se contrazic care aparţin unor grupuri care se termină înainte de poziţia i. Pentru a obţine recurenţa, ne gândim că la poziţia i+1 vom încerca să formăm un nou grup. Are rost să luăm în considerare în acest moment doar acei pitici j cu propritatea că A[j] = i. Găsirea acestora nu presupune o iteraţie liniară, datorită sortării iniţiale. Vom crea mai multe grupuri noi conţinând piticii cu acelaşi B. Să presupunem că un astfel de grup conţine nr pitici. Atunci recurenţa va fi C[N-B[j]] = max(C[N-B[j]], C[i] + min(N-A[j]-B[j], nr)), deoarece grupul se va termina la poziţia N-B[j] şi numărul de pitici din noul grup nu poate depăşi N-A[j]-B[j]. Nu trebuie uitat cazul în care grupul format conţine un singur pitic care minte, caz banal de tratat: C[i+1] = max(C[i+1], C[i]).
Vrejuri
Fie Sm suma totala a vrejurilor la finalul celor K zile daca nu ar fi taiate. Trebuie ca in total sa scadem Sm - S din vrejuri. Pentru ca efortul depus pentru o operatie este patratul a cat taiem, trebuie sa incercam ca suma totala ce trebuie scazuta sa o impartim in taieri cat mai echilibrate (de exemplu daca vrem sa taiem un total de 7 in 3 operatii cel mai bine este 2, 2 si 3). Asadar fie xi totalul pe care vrem sa il taiem din planta i. Vrem ca suma toturor xi-urilor sa fie egala cu Sm - S si xi-ul maxim sa fie cat mai mic posibil. In acelasi timp vrem ca fiecare xi sa fie impartit in cele K zile cat mai echilibrat posibil.
Pentru aceasta putem cauta binar xi-ul maxim pe care il taiem. Fie q aceasta valoare. Din fiecare planta vom taia min( q, Hi + K * Pi ). Fie ST = suma dupa i=1,N din min( q, Hi + K * Pi ). Daca ST < Sm - S atunci q este prea mic. Daca ST > Sm - S atunci q este prea mare. Daca cele doua sunt egale atunci q este valoarea cautata si am descoperit xi = min( q, Hi + K * Pi ), cat taiem din fiecare planta. Tot ce ramane de facut este sa impartim fiecare xi in K valori cat mai egale. Vom avea K - xi mod K valori egale cu xi / K si xi mod K valori egale cu xi / K + 1 (exemplu de mai sus cu valoarea 7 impartita in 3 valori cat mai egale este concludenta). Costul total va fi suma patratelor fiecarei taieturi individuale.
Aceasta solutie are o complexitate N * log val_max, unde val_max este valoarea maxima pe care o poate atinge un vrej. O solutie N * log N se poate obtine daca sortam vrejurile dupa inaltimea finala la care ajung netaiate, si aflam q fara o cautare binara.
Arborest
Se poate observa usor ca atunci cand modificam tatal unui nod, este cel mai bine sa il modificam in radacina arborelului, 1. Putem cauta binar adancimea maxima a arborelui. Vrem ca pentru o anumita adancime maxima q sa aflam nr numarul de mutari necesar pentru a aduce arborele la adancimea maxima q. Daca nr > K atunci q este prea mic. Altfel q poate scadea in continuare. Pentru a afla nr vom proceda in felul urmator. Fie Di distanta de la radacina la nodul i. Sortam toate nodurile descrescator dupa Di. Parcurgem nodurile in ordinea sortarii. Sa zicem ca ne aflam la nodul x. Daca Dx > q atunci nodul x trebuie urcat. Dar pentru ca nodul x este cel mai de jos nod neurcat inca, vrem sa ducem nodul x la nivelul q schimband tatal celui de al q-1-lea tata al lui x. Facem acest lucru pentru a ridica cat mai multe noduri deasupra nivelului q. Fie T al q-1-lea tata al lui x. Pentru a urca intreg subarborele lui T parcurgem acest surarbore si marcam toate nodurile din subarbore ca fiind vizitate. Incrementam nr. Cand trecem la urmatorul nod ce trebuie ridicat, trebuie sa verificam in plus daca a fost vizitat (daca a fost in subarborele vreunui nod ridicat) ca sa stim ca nu trebuie ridicat. Trebuie de asemenea sa avem grija ca atunci cand parcurgem subarborele unui nod ce trebuie ridicat, sa nu revizitam nodurile ce au fost ridicate inainte pentru ca este inutil (sa nu parcurgem subarborii deja ridicati ai subarborelui ce vrem sa il ridicam in acest moment pentru ca nu este necesar; acest lucru ar duce la o complexitate mult mai mare).
Aceasta abordare duce la o complexitate N log N.
Kss
Pentru a rezolva aceasta problema vom incerca o abordare de genul urmator. Daca am putea raspunde la intrebarea: "Avand un prefix oarecare, cate subsiruri distincte incep cu acest prefix?", putem incerca sa cautam fiecare litera pe rand din solutie pana cand gasim intregul sir cerut. Construim o dinamica din[ i ] = numarul de subsiruri distincte care incep de pe pozitia i si contin litera de pe pozitia i. Ca sa rezolvam aceasta dinamica mai intai definim next[ c ][ i ] = prima pozitie dupa i pe care apare caracterul c (daca c apare fix pe pozitia i atunci next[ c ][ i ] = i). Vom calcula dinamica de la pozitia N spre pozitia 1, iar recurenta este: din[ i ] = 1 + suma dupa c = a,z din din[ next[ c ][ i + 1 ] ]. Luam doar prima aparatie a fiecarui caracter pentru ca subsirurile sunt distincte dupa valoare, si nu dupa pozitiile pe care apar caracterele in sirul initial; luam in calcul si cazul cand subsirul contine doar caracterul curent. Avand aceasta dinamica putem incepe sa cautam solutia, pentru ca putem raspunde la intrebarea intiala astfel: daca avem un prefix p, il potrivim ca subsir peste sirul S astfel incat ultimul caracter al lui p apare cat mai repede in S (de exemplu pentru p = a b si S = c a b b vom potrivi c a b b si nu c a b b ). Fie q aceasta pozitie a ultimul caracter din p. Numarul de subsiruri care incep cu acest prefix p este din[ q ] si se observa usor de ce.
In continuare voi explica mai detaliat cum gasim propriu-zis solutia. Dorim sa gasim al K-lea subsir. Sa presupunem mai intai ca sirul nostru incepe cu litera a. Determinam acel q (am explicat mai sus ce reprezinta). Daca cumva din[q] < K atunci inseamna ca solutia nu va incepe cu a ci cu o litera mai mare (lexicografic) pentru ca nu sunt suficiente subsiruri care incep cu a. Scadem din K, din[q] si incercam urmatoarea litera b pentru ca aplicam acelasi rationament (incercam sa gasim al K-din[q]-lea subsir care nu incepe cu a ). Cand din[q] >= K inseamna ca litera curenta este cea buna si atunci trebuie sa gasim urmatoarea (la acest pas trebuie sa scadem 1 din K pentru ca sirul care se termina fix cu litera curenta apare lexicografic inaintea celor ce vor urma, mai lungi). Pentru urmatoarea litera aplicam acelasi rationament decat ca trebuie sa avem grija ca acum inceputul solutiei este un prefix si nu doar o litera. Ne oprim atunci cand K-ul ramas devine 0 (adica tocmai am pus ultima litera).
Solutia aceasta are o complexitate N * sigma pe fiecare test ( sigma este numarul de caractere din alfabet).
Tester
Vom transforma graful rezultat din starile si tastele date astfel: fiecarei taste i ii vom asocia un nod i in noul graf. Oricare doua taste i si j ce pot aparea una dupa alta (sunt de forma ( x, y ) si ( y, z ) ) le vom lega in noul graf cu o muchie orientata de la i la j. Se observa ca in noul graf un combo este reprezentat de o muchie. Faptul ca dorim sa obtinem o secventa cu toate combourile exact odata, adica ce contine toate muchiile exact odata, ne duce cu gandul la o parcurgere euleriana a noului graf. Inainte de a incerca sa construim o parcurgere euleriana a grafului trebuie sa transformam graful intr-unul eulerian. Pentru aceasta procedam in felul urmator. Fie GINi numarul de muchii care intra in nodul i si GOUTi numarul de muchii care ies din nodul I. Stim ca intr-un graf eulerian GINi trebuie sa fie egal GOUTi. Cream un nou nod R din care si spre care tragem cate muchii sunt necesare pentru a satisface conditia de egalitate intre GINi si GOUTi pentru fiecare nod i. Acum putem sa construim un ciclu eulerian incepand din nodul R. Secventa creata este exact secventa de taste ce vor fi apasate de Paraschiva. Orice trecere prin nodul R va reprezenta o resetare a jocului (ea denota trecerea printr-o muchie inexistenta din graf), mai putin prima si ultima care nu sunt treceri ci doar marcheaza inceputul si sfarsitul secventei. Secventa rezultata respecta conditia ca fiecare muchie sa fie parcursa exact odata (fiecare combo sa apara exact odata) si numarul de resetari al jocului va fi minim (nu se poate obtine o secventa cu mai putine resetari din cauza naturii grafului).
Solutia are complexitate N * M.
