Solutii Algoritmiada 2016, Runda 3

Clasament

Clasamentele fiecarui judet pot fi completate in ordinea in care citim datele de intrare, astfel se poate stabili judetul unui participant in functie de participantii aflati inaintea lui. Presupunand ca un concurent oarecare are valoarea X, acesta poate fi atribuit oricarui judet care are in mod curent X - 1 persoane in clasament. Asta inseamna ca numarul de posibilitati pentru a repartiza acest concurent este egal cu numarul de judete cu aceasta proprietate, iar noul rezultat va fi vechiul rezultat inmultit cu acest numar (rezultatul initial avand valoarea 1). Dupa ce participantul va fi atribuit unui judet, numarul judetelor cu X - 1 participanti va scadea cu 1, iar numarul judetelor cu X participanti va creste cu 1. In continuare se va aplica aceeasi regula pentru concurentii ce urmeaza.
Complexitatea algoritmului este O(N).

Examen

Putem privi studentii ca noduri ale unui graf. Daca studentii a si b au suma c, va exista in graf o muchie intre a si b de cost c. Gasim ciclurile din graf (unul sau doua) si le rezolvam independent. Daca un ciclu contine un numar par de noduri atunci are o infinitate de solutii.

Fixam un nod al ciclului si il notam valoarea cu x. Folosindu-ne de sume, exprimam celelalte noduri in functie de x (sub forma ax + b). Fiindca e ciclu, avem o suma in plus din care il putem afla pe x, dupa care aflam restul valorilor.

Nu e nevoie sa reprezenta efectiv graful, structura lui fiind fixa. Vizitam fiecare student o singura data, deci complexitatea solutiei este O(N).

Progresii Colorate

Cerinta 1:
Parcurgem sirul si retinem, pentru fiecare culoare c care apare in datele de intrare, cel mai lung subsir care se termina intr-un k-element care contine culoarea c. Complexitatea este O(N*K).

Cerinta 2:
Fie D numarul de culori diferite care apar in X. Raspunsul este CK - (C-D)K. Din numarul total de k-elemente scadem k-elementele care nu au niciun element comun cu X.
Se poate rezolva si cu programare dinamica.
Complexitatile sunt O(logK) sau O(K).

Cerinta 3:
Generam primele N k-elemente in ordine lexicografica. Trebuie sa ne asiguram ca sirul generat e progresie colorata, in special la trecerea de la elementele de forma x C … C la elementul x+1 1 … 1. Interschimbam elementele de forma x 1 … 1 x+1 cu elementul x C … C. Complexitatea este O(N*K).
Exista si alte strategii de generare.

Comisia

Solutia 1: 100 de puncte
Se va folosi o strategie divide et impera. Se va calcula subsecventa minima pe intervalul (st, dr) folosind urmatorul algorithm:
Definim mij = (st + dr) / 2. Pentru fiecare st ≤ i ≤ mij se va calcula j astfel incat j > mij, subsecventa (i, j) este valida (respecta conditiile date de sirul A), iar j este minim. Este evident faptul ca nu este nevoie sa se verifice subsecvente cu (i, k) cu k > j deoarece suma factorilor de risc pe acest interval va fi mai mare decat cea pe (i, j). In acest mod se va gasi subsecventa de risc total minim care trece prin centru, urmand ca apoi sa se apeleze recursiv algoritmul pe subsecventele (st, mij) si (mij + 1, dr) pentru a gasi subsecventa de risc total minim care nu trece prin centru.
Pentru a calcula aceasta valoare j pentru fiecare pozitie i, mai intai se va calcula P[i] ca fiind pozitia minima astfel incat subsecventa (i, P[i]) respecta toate cerintele din jumatatea stanga. Mai exact P[i] = i + max(A[i], A[i + 1], ... A[mij]) - 1. Simetric se va calcula P[k] pentru k > mid ca fiind pozitia maxima astfel incat subsbsecventa (P[k], k) respecta toate cerintele din jumatatea dreapta, adica P[k] = k - max(A[k], A[k - 1], ... A[mij + 1]) + 1. Astfel, pentru o pozitie i, j va fi valoarea minima k cu proprietatea P[i] <= k si i <= P[k].
Pentru a afla rapid aceasta valoare se poate folosi o structura care poate calcula rapid minimul pe un interval in timp ce modificam valori, de exemplu arbori de intervale sau arbori indexati binari. Se va porni de la i = mij si i va descreste pana cand va capata valoarea st. In acelasi timp se vor pune in structura numerele k cu proprietatea P[k] = i (cele cu P[k] > i fiind deja puse in pasii anteriori), iar pentru a afla j se gasi minimul din intervalul (P[i], dr) care se afla in structura.
Folosind arbori de intervale sau arbori indexati binari, complexitatea pe fiecare adaugare/interogare va fi O(log N), deci per total complexitatea algoritmului este O(N log2 N).

Solutia 2: 100 de puncte
Se vor verifica mai intai toate subsecventele care contin elementul maxim (dintre valorile sirului A). Daca exista mai multe elemente cu valoare maxima, se poate alege unul oarecare. Sa presupunem ca acesta se afla pe pozitia P. Numarul de subsecvente valide (care respecta cerintele date de sirul A) in care este inclus si elementul P este min(P, N - P + 1) deoarece aceaste subsecvente trebuie sa aiba lungimea A[P]. Acest element imparte sirul in alte doua siruri cu P - 1 elemente, respectiv N - P elemente. Se va aplica algoritmul recursiv algoritmul de mai sus pe cele doua siruri noi obtinute, acum verificand toate subsecventele care nu contin elementul de pe pozitia P.
Daca notam numarul de pasi pentru a rezolva intervalul (st, dr) cu C[st, dr], atunci aceasta valoare este egala cu numarul subsecventelor verificate (presupunand ca le verificam in timp constant).
C[st, dr] = C[st, P - 1] + C[P + 1, dr] + min(P - st + 1, dr - P + 1), unde P este pozitia maximului din intervalul (st, dr).
Acest algoritm se comporta asemanator algoritmului Heavy Path Decomposition avand complexitatea O(N log N)

Solutia 3: 100 puncte
O alta abordare a acestei probleme ar fi de tip greedy. Vom defini functia max_intr(l, r) = max(A[i]| l <= i <= r).
Pentru orice inceput de secventa l ( 1 <= l <= n ) este necesara gasirea capatului r ( l <= r <= n ) minim astfel inca sa se respecte conditia r - l + 1 >= max_intr(l, r). Odata ce am gasit secventa minima ce incepe in l puteam actualiza raspunsul cu suma din B pe intervalul [l, r].
Initial consideram l = r si ne extindem cu r atat timp cat este nevoie. Mai exact, daca max_intr(l, r) > r - l + 1 atunci r va deveni l + max_intr(l, r) - 1 si asa mai departe pana cand max_intr(l, r) <= r - l + 1 .
In worst case sirul va fi : 2 3 4 5 6 .. n n.

  • In primul pas l = 1, r va lua valorile {1, 2, 3, 4, ... , n}
  • In al doilea pas l = 2, r va lua valorile {2, 4, 6, 8, ... }
  • In al treilea pas l = 3, r va lua valorile {3, 6, 9, 12, ... }

In total algoritmul va face n + n/2 + n/3 + .. pasi care este aproximat la O(n log n).
Pentru a calcula rapid max_intr(l, r) e nevoie de o structura de tip Range minimum query.
Complexitate finala O(n log n).
Sursa demonstrativa : Comisia

Cuplaje

Vom aborda o strategie de tip greedy. Sortam baietii dupa cat de pretentiosi sunt. Ii parcurgem incepand cu cel mai pretentios pana la cel mai putin pretentios. Daca baiatul curent este dispus sa se cupleze cu o fata atunci orice alt baiat care urmeaza va fi de asemenea dispus sa se cupleze cu aceasta. De aceea, putem mentine la fiecare pas o multime de fete cu care s-ar cupla baiatul curent. Dintre fetele care s-ar cupla cu baiatul curent (o parte din multime), o alegem tot timpul pe cea mai pretentioasa. Nu ar avea sens sa alegem una mai putin pretentioasa fiindca dorim sa imbunatatim sansele urmatorilor baieti.

Ne vom mentine fetele intr-o structura de date care ne permite sa extragem eficient elementul minim mai mare sau egal cu un numar dat (set, arbore de intervale etc). Complexitatea solutiei este O(NlogM + MlogM).

Numerologie

Problema se poate reduce la mai generalul set cover. Aceasta fiind NP-Hard pe cazul general iar cei mai buni algoritmi exponenţiali fiind mult prea înceţi, este clar că această reducere nu ne este de folos. Este, deci, foarte probabil ca soluţia să folosească proprietăţi specifice ale numerelor prime, care fac problema uşor mai tractabilă.

Mai exact, deoarece fiecare număr natural limitat superior de M are un singur factor prim mai mare sau egal cu sqrt(M), putem trata numerele prime mici (mai mici decât sqrt(M)) şi pe cele mari independent. Observăm că dacă avem hotărâtă submulţimea de numere prime mici pe care le cumpărăm, pentru fiecare număr X neacoperit există două cazuri: acesta are un factor prim mare, caz în care suntem obligaţi să-l cumpărăm şi pe acesta, deoarece nu avem alte variante de-al acoperi pe X, respectiv cazul în care X nu are un factor prim mare, ceea ce înseamnă că submulţimea curentă de numere prime mici nu ne poate duce la o soluţie viabilă.

Din fericire, există doar 11 numere prime mai mici decât sqrt(1250), ceea ce ne permite să încercăm toate submulţimile posibile, iar pentru fiecare dintre acestea să iterăm peste toate cele N numere pentru a cumpăra eventualele numere prime mari necesare. Folosind teorema numerelor prime, obţinem o complexitate generală O(2 (sqrt(M) / log(M)) * N).

Sortop