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(N²) si memorie O(1)

Soluţie `100` de puncte

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

Avem 2 cazuri:

N = 2 * K =>
N = K² - K² + 2 * K + 1 - 1
= (K² + 2 * K + 1) - K² - 1
= (K + 1)² - K² - 1
= f(K + 1) + f(-K) + f(-1)

N = 2 * K + 1 =>
N = (K + 1)² - K²
= 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 X_i. Dacă nu am pus niciun segment pe o dreapta i atunci X_i = 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 X_i astfel încât X_i <= 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).

No such page: algoritmiada-2012/runda-2/solutii/subgraf

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 * K²)
Memorie: O(M * K)

infoarena informatica de performanta