Solutii Algoritmiada 2012, Runda 2

Triplet

Soluţie 40 de puncte

Se observa destul de usor ca putem gasi solutie astfel incat si X si Y si Z sa fie mai mici sau egale cu N in modul. Astfel ii putem fixa pe X si Y in [-N, +N] si sa testam daca exista Z astfel incat f(Z) = N - f(X) - f(Y)

Complexitate: timp O(N2) si memorie O(1)

Soluţie 100 de puncte

Folosim formula (K + 1)2 = K2 + 2 * K + 1.

Avem 2 cazuri:

  • N = 2 * K =>
    N = K2 - K2 + 2 * K + 1 - 1
    = (K2 + 2 * K + 1) - K2 - 1
    = (K + 1)2 - K2 - 1
    = f(K + 1) + f(-K) + f(-1)
  • N = 2 * K + 1 =>
    N = (K + 1)2 - K2
    = f(K + 1) + f(-K)
    = f(K + 1) + f(-K) + f(0)

Complexitate: timp si memorie O(1)

Secvmin

Deoarece elementele din şirul B sunt distincte, putem ţine un vector C[X] = poziţia în vectorul B al elementului X.

Parcurgem şirul A de la stânga la dreapta şi la fiecare element i ţinem dinamica D[X] = cea mai scurtă subsecvenţă din şirul A care se termină în i, astfel încât subsecvenţa [1, C[X]] din B să apară ca subşir. Practic, vrem cea mai scurtă subsecvenţă care se termină într-un elementul cu valoarea X. Pentru simplitate, nu o să ţinem lungimea celei mai scurte subsecvenţe, ci capătul stanga al acesteia. Definim p = C[A[i]] ca fiind poziţia elementului curent A[i] în vectorul B. La fiecare pas i avem urmatoarele modificări:

  • D[A[i]] = i, dacă p = 1 (am găsit un nou posibil capăt stânga)
  • D[A[i]] = D[B[p - 1]], dacă p ≠ 1. Mai exact, după ce am inserat un nou element A[i] care se află pe poziţia p în B, răspunsul în D[A[i]] devine capătul stânga al elementului precedent din B, adică elementul de la poziţia p - 1, cu valoarea B[p - 1].

Dacă p = M (lungimea şirului B), putem considera că avem o nouă soluţie care începe la poziţia D[A[i]] şi se termină la poziţia i, lungimea acesteia fiind D[A[i]] - i + 1. Desigur, la final considerăm doar cea mai scurtă subsecvenţă dintre toate.

Complexitate: O(N).

Planificare

Problema ne cere să aşezăm cât mai multe intervale pe un anumit număr de drepte astfel încat aceste intervale să nu se intersecteze.

Reţinem fiecare capăt de interval ca pe un eveniment de intrare-ieşire. Capătul stânga al unui interval este un eveniment de intrare, în timp ce capătul dreapta îl considerăm a fi un eveniment de ieşire. Sortăm evenimentele după poziţia lor pe axă şi avem 2 cazuri:

  • Începe un interval nou (eveniment de intrare): Menţinem o structură de tip multiset în care ne salvăm toate intervalele pe care momentan dorim să le folosim, dar este posibil sa ne răzgândim. Dacă această structură are mai puţin de K elemente salvate, nu avem nici un motiv să nu inserăm noul interval din moment ce avem suficient loc. În cazul în care acem deja K elemente ocupate în multiset, putem introduce noul interval doar daca îl înlocuim cu un altul. Astfel, trebuie sa deducem un criteriu după care să decidem dacă un interval X este mai bun decât un interval Y. Observăm faptul că nu ne interesează capătul stânga al intervalelor din moment ce le-am baleat, capătul dreapta rămânând singurul criteriu de comparaţie. Un interval cu un capăt dreapta mai mare este mai prost deoarece va fi eliberat mai târziu decât unul cu un capăt dreapta mai mic. Mai exact, dacă intervalul pe care am vrea sa îl inserăm are capătul dreapta mai mare decât toate celălalte din multiset, este clar cel mai prost şi îl ignorăm. În schimb, dacă există un interval în multiset cu un capăt dreapta mai mare, înlocuim cel mai prost element din structura noastră cu noul interval determinat.
  • Se termină un interval (eveniment de ieşire): Dacă intervalul încă se află în multiset, înseamnă că pe tot parcursul evenimentelor de când a fost inserat, intervalul a rămas un posibil candidat care nu a fost înlocuit de nici un alt interval. Ca urmare, scoatem intervalul din multiset şi îl numărăm la soluţie. Astfel, se eliberează un loc în multiset. Dacă elementul nu se mai află în multiset, înseamnă că la un moment dat a fost înlocuit (sau nu a fost inserat de la bun început) şi nu este nevoie sa facem nimic.

Soluţie alternativă:

Pentru a rezolva această problemă vom folosi o strategie greedy. Sortăm toate intervalele crescător după capătul din dreapta, le parcurgem şi încercăm să adăugăm intervalul curent la soluţie. Să presupunem că intervalul nostru este [L, R] şi ştim pentru toate dreptele care este cel mai din dreapta segment de pe ea, capătul din dreapta al acestui segment să îl numim Xi. Dacă nu am pus niciun segment pe o dreapta i atunci Xi = 0. Vom încerca să adăugăm intervalul curent fără să înlocuim alte intervale deja adăugate. Pentru a avea o aşezare optimă vom alege dreapta cu cel mai mare Xi astfel încât Xi <= L. Putem ţine un multiset pentru a găsi această dreaptă în O(log K).
Este evident faptul că nu este favorabil să înlocuim segmente deja puse cu segmentul curent deoarece numărul de intervale de până acum nu va creşte (eventual va scădea dacă substituim mai multe segmente) şi nu ne va ajuta nici la paşii următori deoarece capătul din dreapta al acestui segment este mai mare decât capătul din dreapta al segmentului înlocuit şi atunci se va suprapune cu mai multe segmente dintre cele care vor urma.

Complexitate O(N log N + N log K).

Subarbore

Observăm că numărul de noduri speciale T este foarte mic, deci problema admite o soluţie exponenţială. Vom construi următoarea dinamică: D[i][j] = dimensiunea minimă a unui subarbore care conţine nodurile speciale corespunzătoare biţilor de 1 din configuraţia binară a lui i, şi are rădăcina în nodul j. Avem două metode prin care putem construi un astfel de subarbore:

  1. Unim doi subarbori mai mici care au rădăcina în acelaşi nod j şi acoperă două mulţimi disjuncte de noduri speciale.
  2. Având un subarbore cu rădăcina în alt nod x, adăugăm un lanţ de la nodul j la nodul x.

Astfel, recurenţa noastră devine:

D[i][j] = minim din:

  • D[i1][j] + D[i2][j], unde i1 or i2 = i (submulţimile i1 şi i2 reunite dau submulţimea i) şi i1 and i2 = 0 (submulţimile sunt disjuncte). Submulţimile pot fi găsite de exemplu, găsind mai întâi pe i1 astfel încât să fie o submulţime a lui i, iar apoi aflăm pe i2 = i - i1;
  • D[i][x] + Dist[j][x], unde în matricea Dist avem precalculate distanţele între oricare două noduri din arbore. Această precalculare poate fi făcută aplicând algoritmul Roy-Floyd.

Este important ca, pentru orice stare i, să calculăm întâi dinamica pentru toate rădăcinile j bazându-ne pe prima parte a recurenţei (unirea a doi arbori) şi abia apoi pe a doua (prelungirea unui lanţ) deoarece rezultatele celei de-a doua recurenţe depind de cele obţinute din prima.

Complexitate: O(3T*N + 2T*N2) timp şi O(2T*N) memorie.

Kgraf

Vom calcula următoarea dinamică: D[i][j][k] = costul maxim al unui lanţ pe care il putem obţine presupunând că am ajuns în nodul i şi am selectat j minime, respectiv k maxime. Dacă ne aflăm în nodul i, putem să continuăm drumul pe lanţ în orice nod X, vecin al lui i, iar acesta poate să fie considerat atât minim, cât şi maxim (sau niciuna). Deci din starea (i,j,k) putem să mergem în orice stare de tipul (X, j, k), (X, j + 1, k), (X, j, k + 1) şi (X, j + 1, k + 1), unde X este un vecin în graf al lui i.

Este destul de neintuitiv de ce această dinamică este corectă deoarece considerăm şi stări invalide în care, de exemplu, cel mai mare element din graf este posibil să îl considerăm la un moment dat în grupa celor mai mici elemente, sau invers. Din fericire, acest lucru nu ne afectează. Considerând o stare invalidă este doar în dezavantajul nostru şi nu va putea depaşi costul unei configuraţii optime. Mai exact, deoarece costul unui lanţ este suma celor mai mari K elemente minus suma celor mai mici K, daca introducem în grupa maximelor un element mai mic (care nu ar avea ce căuta acolo), costul o să fie mai mic decât atunci când considerăm chiar pe cele mai mari K elemente. Asemănător, dacă introducem în grupa minimelor un element mai mare, costul o sa scadă cu mai mult decât ar trebui în realitate, rezultatul fiind mai mic decât cel optim. Ca urmare, deşi luăm în calcul atât stări valide cât şi invalide, răspunsul optim generat de o configuraţie validă nu poate să fie mai mic decât unul generat de o configuraţie invalidă, deci nu dăunează dacă le considerăm pe ambele.

Deoarece nu avem suficientă memorie, dinamica trebuie facută D[i][j][k] = costul maxim al unui lanţ care se termină în nodul j cu i minime si k maxime selectate. Astfel, putem ţine doar ultimele 2 linii din această matrice tridimensională.

Timp: O(M * K2)
Memorie: O(M * K)