Solutii Algoritmiada 2016, Runda 1

Subsir binar

Observam ca, pentru a avea un rezultat cat mai mic, putem apela la o strategie greedy. Daca unui bit Bi ii asociem o pozitie p in A, lui Bi + 1 ii putem asocia cea mai mica pozitie l astfel incat Bi + 1 = Al si p < l. Astfel, putem folosi algoritmul urmator.
Tinem un indice k care indica pozitia actuala din sirul B, initial acesta este egal cu 1. Parcurgem toate numerele incepand de la 0, iar pentru fiecare numar o sa parcurgem bitii lui descrescator incepand de la cel mai mare bit egal cu 1. Daca bitul curent este egal cu Bk , atunci incrementam k. Numarul total de biti parcursi in momentul cand k devine |B| + 1 va fi raspunsul la cerinta problemei.

KBetray

O sa aplicam o strategie greedy in felul urmator: Consideram toate maximele curente si le facem suma. Pentru a mari aceasta suma, o sa selectam cel mai mic maxim si o sa il inlocuim cu cel mai mare minim (doar daca cel mai mare minim este mai bun, altfel ne oprim deoarece nu suntem obligati sa folosim toate interschimbarile). Putem ori sa tinem o structura de tip heap pentru a extrage minimul/maximul dintr-o lista, ori in cazul de fata putem doar sorta minimele si maximele si sa iteram prin acestea. Atentie doar sa nu interschimbati cel mai prost maxim cu cel mai bun minim de mai mult de K ori. Complexitatea totala: O(N log N)

Starcity

Sa presupunem ca in configuratia initiala si cea finala nodul 1 este liber. In acest caz putem scapa de nodul 1 din configuratie, iar o operatie va consta in mutarea unei valori dintr-un nod in unicul nod liber. Aceasta operatie este echivalenta cu mutarea valorii din nodul ales mai intai in nodul 1 si apoi in nodul liber cu indice diferit de 1, deci operatia noastra va avea cost 2 in final.
Acum, configuratiile noastre vor avea N - 1 numere, de la 0 la N - 2. In loc de 0 vom scrie N - 1 pentru a avea o permutare de lungime N - 1. Ca sa ne fie mai usor, o sa schimbam configuratia finala in permutarea elementara (permutarea in care P[i] = i) si vom schimba si configuratia initiala astfel incat operatiile facute pe configuratiile nemodificate sa aiba echivalent in noile configuratii. De exemplu, sa presupunem ca avem configuratiile:
2 3 1 4 - initiala
4 2 1 3 - finala
Putem schimba 2 coloane intre ele si o sa transformam configuratia finala in permutarea elementara:
1 3 4 2 - initiala
1 2 3 4 - finala
Acum trebuie sa aducem permutarea initiala la cea elementara avand voie sa schimbam valoarea N - 1 cu oricare alta. Avem 2 cazuri:

1. Elementul N - 1 se afla pe pozitia N - 1.
Pentru o pozitie i unde P[i] ≠ i, valoarea P[i] trebuie sa ajunga pe pozitia P[i], valoarea de pe pozitia P[i] trebuie sa ajunga pe pozitia P[P[i]] ... valoarea de pe pozitia P[P[P...P[i]] trebuie sa ajunga pe pozitia i. Observam ca aici s-a format un ciclu. Pentru a duce toate valorile pe pozitiile lor, vom interschimba prima data valoarea de pe pozitia i cu valoarea de pe pozitia N - 1. Acum pe pozitia i se afla valoarea N - 1 si pe pozitia N - 1 se afla valoarea care anterior era P[i]. In acest mod am introdus valoarea N - 1 in ciclu. Vom aduce pe pozitia i valoarea i, acum valoarea N - 1 este pe o alta pozitie. O sa aducem repetat pe pozitia unde se afla N - 1 valoarea care trebuie sa fie in acea pozitie(practic valoarea care este egala cu indicele pozitiei) pana cand valoarea N - 1 o sa ajunga pe pozitia lui (adica pozitia N - 1). Facem aceste operatii pentru fiecare ciclu si vom ajunge la permutarea elementara. Costul rezolvarii unui ciclu de marime K este de K + 1.
2. Elementul N - 1 nu se afla pe pizitia N - 1.
In acest caz e ca si cum noi am fi interschimbat deja valoarea de pe o pozitie i cu N - 1, deci vom rezolva prima data ciclul care contine elementul N - 1 si apoi ne vom ocupa si de celelalte folosind aceeasi metoda ca in primul caz.
Complexitatea acestul algoritm este O(N).

Revenind in cazul de baza, sa presupunem ca nodul 1 din configuratia initiala nu este liber. In acest caz exista doua noduri libere diferite de 1, deci avem doar doua posibile mutari. Vom muta mai intai valoarea din nodul 1 intr-unul din noduri si vom aplica algoritmul de mai sus, apoi il vom muta in celalalt nod liber si vom aplica algoritmul. Din cele doua secvente de mutari obtinute o vom alege pe cea cu cardinal minim. In mod similar se trateaza si cazul in care nodul 1 din configuratia finala nu este liber.

Vom rula algoritmul de mai sus de maxim 4 ori, deci complexitatea finala va fi O(N).

Produse

Soluţie 15 puncte

O soluţie brute-force ar trebui să ia 15 puncte. O alternativă ar fi să incercăm prin programare dinamică

count[N][D] = numărul de submulţimi cu produsul egal cu D format din primele N elemente. Recurenţa este straight forward:
count[N][D] = count[N - 1][D] + count[N - 1][D / v[N]], dacă (D % v[N] == 0), cazul de bază fiind count[ 1 ][p * v[ 1 ]] , p * v[ 1 ] <= D

Soluţia este suma liniei N din matricea obţinută prin programare dinamică.

Solutie 45 puncte

Se observă că in dinamica de mai sus avem nevoie doar de pasul anterior deci nu este nevoie să ţinem în memorie decât 2 linii ale matricii.
Datorită faptului că la elementul curent adăugam mereu un element de pe o coloana mai mică decât coloana aceasta putem să reţinem o singură linie, deci acum dinamica noastră s-a transformat în:

count[D] = numărul submulţimilor cu produsul egal cu D construite cu elementele de până acum.

Pentru a popula vectorul count vom folosi un algoritm similar cu acela de la ciurul lui erasthotenes, doar că parcurgem vectorul count de la final către început. Algoritmul este următorul:

for X in input {
    if (X != 1) {
        biggestMultiple = (K / X) * X // cel mai mare multiplu de X mai mic sau egal cu K
        for (idx = biggestMultiple; idx > X; idx -= X)
            count[idx] += count[idx / X]
        count[X] += count[1]
     }
}

Rămâne să vă gandiţi voi la cât este count1.
Numărul de operaţii executate de acest algoritm este O(N * (1 / v[1] + 1 / v[2] + ... + 1 / v[N])) care, în cazul cel mai defavorabil este O(N2). Dacă numerele din input sunt uniform distribuite atunci complexitatea este aproximativ O(N * log(N)).

Soluţie 100 puncte

După cum am spus mai sus, dacă numerele din input sunt uniform distribuite complexitatea algoritmului de mai sus devine O(N * log(N)).
Worst case-ul algoritmului se atinge când sunt multe numere egale în input. De aici ne vine ideea de a folosi fiecare număr distinct din input o singură dată. În acest caz numărul maxim de operaţii care va fi făcut de algoritm va fi O(N * log(N)) în cazul în care toate elementele din input sunt distincte.
Algoritmul rămâne acelaşi doar că se iterează doar că se iterează doar peste numerele distincte din input iar update-ul pentru count[idx] se face folosind cateva elemente de combinatorică de bază bazate pe frecvenţa de apariţie a numerelor din input.

Infinite Pattern Matching

Solutia de 56 de puncte

Daca generam sirul A astfel incat sa contina toate numerele de pana al 20 de biti atunci contine toate combinatiile specifice de 1, 2, ..., 20 de biti.
Putem sa generam prefixul de aceasta lungime, sa il notam cu P, si dupa sa cautam prima pozitie a lui B in P. (Pentru cei care programeaza in C++ si folosesc STL functia string::find face exact asta, si era mai mult decat suficient sa rezolve problema).

Complexitate O(raspuns) cand folosim KMP sau Z-algorithm sa cautam sirul, sau O(raspuns * |B|) cand folosim ceva mai rudimentar ca string::find sau strstr.

Solutia de 100 de puncte

Mai intai trebuie sa scapam de un caz particular. Daca sirul B e format numai din zerouri prima oara cand cand apare in A e cand scriem numarul 2|B|.

În continuare vom avea 3 cazuri principale. Le vom proba pe toate 3 si vom actualiza raspunsul minim.

  • Sirul B este format din reprezentarea in baza 2 a unui singur numar, chiar numarul B. Deci prima pozitie pe care apare B in acest caz e pozitia pe care apare numarul B.
  • Sirul B este format din reprezentarea in baza 2 a doua numere. Stim ca orice numar incepe cu bitul 1 deci putem itera prin bitii lui B si sa marcam unde credem ca incepem al doilea numar si care e lungimea acestui numar. Astfel daca cele doua numere consecutive sunt X si Y (X = Y - 1) B va fi egal cu un sufix de-al lui X concatenat cu un prefix de-al lui Y.
    Putem obtine Y luand sufixul lui X si adunand 1 ca sa ii obtinem bitii lipsa. Dupa doar verificam ca e corect.
    • Un subcaz particular e cand Y = 1 (pentru ca X ar fi 0 si asta ar fi gresit, sirul A incepe de la 1 in sus).
  • Sirul B este format din reprezentarea in baza 2 a trei sau mai multe numere. De aici deducem ca cel putin unul din aceste numere apare in intregime in sirul B. Putem fixa toate pozitiile unde poate fi un numar in intregime si dupa sa generam destule numere in continuare (si inapoi) si sa verificam ca la cazul cu B format din 2 numere.
    • Din nou avem un subcaz particular cand prima bucata din B va fi formata din numarul 0 (adica B e un prefix a lui '0' concatenat cu A).

Complexitatea acestei solutii este fie O(N3), fie O(N4) in functie de implementare. Ambele solutii obtineau punctajul maxim.

De mentionat ca exista si o solutie in O(N2), dar am considerat ca e greu de departajat de solutii foarte optimizate in O(N3) sau O(N4) si implementarea era greoaie. Lasam aceasta solutie ca exercitiu pentru cititor.

Seriale

Prima observatie se bazeaza pe faptul ca nu trebuie sa ne punem problema unde o sa inseram un element nou. Acest lucru se datoreaza faptului ca oricare ar fi lista noastra finala, elementele din lista 2 pot fi inserate teoretic oriunde astfel incat sa dea bine. Ramane sa ne punem problema ce elemente sa introducem.

O sa fixam in O(n) numarul x, reprezentand faptul ca avem de gand sa eliminam din lista initiala cele mai mici x elemente. Pe masura ce x creste, o sa mentinem cu un pointer valoarea y, reprezentand numarul minim de elemente maxime pe care trebuie sa le eliminam din lista 1, astfel incat dupa ce am eliminat x elemente minime si y elemente maxime, lista sa devina sortata. Pentru a putea mentine acest y este suficient sa tinem un set cu indicii elementelor nesterse si verificam de fiecare data cand vrem sa inseram un element daca indicele din stanga are valoare mai mica si indicele din dreapta are valoare mai mare.

Ramane sa verificam daca pentru un x si un y fixat putem sa gasim o strategie de a selecta elemente din lista 2. O sa impartim elementele din lista 2 in 3 grupe: elemente care atunci cand le inseram ne adauga un minim ( x creste), elemente care atunci cand le inseram ne adauga un maxim ( y creste), elemente intermediare care se afla intre cele mai mici x elemente si cele mai mari y elemente. Cu cate o cautare binara putem numara Min (numerele de tipul 1, le numim elemente de tip Min), Max (numere de tipul 2, le numim elemente de tip Max), Mid (numerele de tipul 3, le numim elemente de tipul Mid). Din momemt ce vrem sa scapam de cele x + y elemente cat mai repede, este clar ca preferam sa nu selectam niciun element de tip Min sau Max. Concluzia este ca mai intai o sa irosim toate Mid-urile. Presupunand ca acestea nu sunt suficiente pentru a ne scapa de cele x + y elemente, trebuie sa adaptam strategie folosind doar Min-uri si Max-uri. Notam xp si yp numarul de minime respectiv maxime ramase dupa folosirea Mid-urilor. Strategia finala este una relativ simpla. Din moment ce nu putem sa luptam la 2 capete in paralel (altfel ar dura la infinit), o sa avem 2 cazuri. Scapam mai intai de toate minimele si dupa de toate maximele, sau invers. Mai exact, o sa introducem Max-uri pana am scapat de toate minimele (minimele sau redus astfel la xp = 0, in timp ce maximele au crescut), dupa care introducem doar Min-uri pana cand am scapat de toate maximele. Pentru celalalt caz ar fi fix invers.

Odaca ce avem x si y fixat, calculam Min, Max si Mid. Strategia nu este nevoie sa fie simulara, ci doar verificata daca avem sau nu suficiente elemente din fiecare tip. Complexitatea totala este O(N * log N). Pentru 60 de puncte puteti simula efectiv operatiile obtinand o complexitate de O(n^2).

Taxi2

Mai intai sa vedem cum se calculeaza costul pentru o anumita configuratie de clienti si taximetristi.

Aici era important sa observam ca pentru o muchie stim exact cate perechi clienti-taximetristi trec prin acea muchie.
Daca de o parte a muchiei sunt A taximetristi si B clienti atunci prin acea muchie vor trece exact min(A, M - B) + min(B, M - A) (lasam demonstratia acestei formule ca exercitiu pentru cititor).

De aici o idee care ne putea veni e sa fixam pentru fiecare muchie cati taximetristi si clienti sunt de o parte. Sa zicem ca avem o muchie de lungime D care imparte arborele in 2 componente cu N1 si N2 noduri. Putem fixa cat taximetristi (A) si clienti (B) sunt in partea cu N1 noduri si stim sigur ca asta va adauga la raspuns: (min(A, M - B) + min(B, M - A)) * Combinari(M, A) * Combinari(M, B) * N1(A + B) * N2(M - A + M - B) * D

Implementarea eficienta a acestui calcul se ptuea face in O(N * M2) si aducea 70 de puncte.

Pentru 100 de puncte se poate observa ca oricum am interschimba un taximetrist si un client raspunsul nu se schimba (din nou, lasam asta ca exercitiu pentru cititor). De aici deducem ca nu trebuie sa fixam clienti si taximetristi de o parte si de alte a unei muchii ci doar oameni de o parte(sa notam asta cu A ≤ 2 * M). Formula pentru o muchie devine min(A, 2 * M - A) * Combinari(2 * M, A) * N1A * N2(2 * M - A) * D

Complexitatea acestei solutii este O(N * M).