Solutii Algoritmiada 2016, Runda 1

K-Lexicografic

Fie dinamica D[i] = numarul de siruri distincte pe care le putem obtine pe intervalul de pozitii [i, N]. Putem varia indicele j, reprezentand cel mai lung prefix comun intre sirul nostru A[i..j] si sirul B[i..j]. Pentru a genera o solutie corecta, j trebuie sa fie mai mic strict decat K. Pentru elementele de la i pana la i + j - 1 avem solutie unica (A[k] = B[k], i ≤ k ≤ i + j - 1). Elementul de pe pozitia i + j trebuie sa fie obligatoriu mai mare strict ( A[i + j] < B[i + j] si avem 'z' - A[i + j] astfel de solutii), iar restul elementelor trebuie doar sa respecte proprietatea problemei in continuare (deci ne uitam in D[i + j + 1]).

Recurenta: D[i] = Suma(('z' - A[i + j]) * D[i + j + 1], 0 ≤ j ≤ K - 1)
Observatie: Pentru ultimile K - 1 elemente nu avem restrictii, deci D[i] = 26N - i + 1 , N - K + 2 ≤ i ≤ N

Aceasta solutie are complexitate O(N * K) si obtine 40 de puncte

Pentru a optimiza solutia, impartim problema in 2 cazuri:

  • Elementul de pe pozitia i este strict mai mare decat A[i], numarul de solutii fiind ('z' - A[i]) * D[i + 1]
  • Elementul de pe pozitia i este egal cu A[i]. Pentru acest caz o sa consideram toate solutiile de la i + 1, din care trebuie sa scadem solutia in care intervalul A[i..i + K - 1] = B[i..i + K - 1] (este identic cu cazul in care j = K).

Recurenta devine: D[i] = ('z' - A[i]) * D[i + 1] + D[i + 1] - ('z' - A[i + K]) * D[i + K + 1]

Aceasta solutie are complexitate O(N) si obtine 100 de puncte

Mayonaka

Impartim query-urile in 2 mari categorii: query-uri cu saltul mai mare ca sqrt(N) si query-uri cu saltul mai mic.

  • Pentru query-urile cu saltul mai mare ca sqrt(N) putem face brute force. Numarul de pasi este maxim N / sqrt(N) <= sqrt(N) per query, deci avem complexitate O(N * sqrt(N)) pentru toate query-urile de acest tip.
  • Pentru query-urile cu saltul mai mic ca sqrt(N) o sa aplicam smenul lui Mars de sqrt(N) ori. Mai exact, impartim aceste query-uri in sqrt(N) categorii, in functie de lungimea saltului. Pentru fiecare categorie dorim sa updatam toate query-urile din acea categorie cu ajutorul smenului lui Mars. Singura diferenta fata de smenul lui Mars clasic este faptul ca pentru un element x, elementul precedent de la care primeste valoare este x - salt (practic, sumele partiale se fac din salt in salt si nu din 1 in 1). Aplicand smenul lui Mars de sqrt(N) ori obtinem complexitate O(N * sqrt(N)) pentru toate query-urile de acest tip.

Complexitate finala: O(N * sqrt(N))

Rating

Se poate observa faptul ca pentru fiecare concurs, lista ratingurilor curente este o solutie valida. Acest lucru se datoreaza faptului ca daca X l-a invins pe Y si a obtinut rating mai mare, este irelevant daca inainte a avut rating mai mare sau nu.

Complexitate este O(N * M * log N) de la sortarea celor M liste.

Revsecv

O idee ar fi sa numaram cate perechi de subsecvente identice exista, prima fiind din sirul A, iar a doua fiind din sirul inv(A), unde am notat cu inv(A) inversul sirului A.
Notam cu lcp(A, B) cel mai lung prefix comun al sirurilor A si B.
Definim sirul B = A + '#' + inv(A), mai exact sirul B este sirul A la care se adauga caracterul '#', iar apoi inversul sirului A. Fie S sirul sortat al sufixelor lui B. Se observa ca lcp(Si, Sj) cu i < j este egal cu min(lcp(Sk, Sk + 1)) pentru oricare i ≤ k < j. Se poate folosi o stiva in care vom tine sortate crescator valorile lcp(Si, Si + 1) pentru a calcula pentru fiecare pozitie i cel mai mare indice, sa il numim lefti, astfel incat
lcp(Slefti, Slefti + 1) < lcp(Si, Si + 1). Similar calculam righti, cel mai mic indice mai mare decat i astfel incat lcp(Srighti, Srighti + 1) < lcp(Si, Si + 1). Avand aceste valori calculate, se stie ca pentru oricare i, oricare pereche de sufixe j si k cu lefti < j, k ≤ righti are proprietatea ca lcp(Sj, Sk) ≥ lcp(Si, Si + 1).
Fie p = min(lcp(Slefti, Slefti + 1), lcp(Srighti, Srighti + 1)) si r = lcp(Si, Si + 1). Se pot numara toate perechile de subsecventele cu lungime in intervalul [p + 1, r] specifice sufixelor din intervalul (lefti, righti]. Daca exista s1 sufixe specifice sirului A (care incep inainte de caracterul '#') si s2 sufixe specifice sirului inv(A) (care incep dupa caracterul '#'), atunci vor exista s1 * s2 * (r - p) perechi de subsecvente.
De observat este faptul ca, daca lcp(Si, Si + 1) = lcp(Si + 1, Si + 2), atunci lefti = lefti + 1 si righti = righti + 1. De aceea, in cazul in care exista mai multi indici i cu aceeasi pereche (lefti, righti) se vor numara subsecventele numai pentru unul din acesti indici.
Pentru a sorta sufixele si pentru a folosi operatia lcp se poate folosi structura Suffix Arrays.

In continuare se vor scadea perechile de subsecvente care se intersecteaza. Se observa ca o pereche de astfel de subsecvente formeaza un palindrom. Astfel, intr-un palindrom de lungime 2 * k se vor afla k perechi, iar intr-un palindrom de lungime 2 * k - 1 vor exista k perechi. Pentru a scadea aceste perechi eficient, vom calcula folosind algoritmul lui Manacher(problema PScPld) cel mai lung palindrom cu centrul in pozitia i sau intre pozitiile i si i + 1. Pentru fiecare palindrom de lungime 2 * k sau 2 * k - 1 vom scadea k2.
De notat este faptul ca am numarat de doua ori fiecare pereche.

Complexitatea primei parti a algoritmului este O(N log2 N), iar a partii a doua este O(N), complexitatea intregului algoritmului fiind O(N log2 N).

Romania

Pentru cazul in care K = 1 si N >= 4 se poate trasa muchie de la singurul varf cu grad de iesire pozitiv la oricare din celelalte varfuri(exceptand vecinii lui). Pentru orice configuratie cu K >= 2 si K <= N - 3 se observa ca exista cel putin un varf cu grad 0, avand un vecin cu grad mai mare decat 0. Se poate trasa muchie de la acest vecin la celalalt vecin al varfului cu grad 0. In acest mod, nodul cu grad 0 poate fi scos din configuratie, cea ramasa avand N - 1 noduri si suma gradelor varfurilor K - 1. Repetand acest proces o sa ajungem la cazul elementar in care K = 1 si N >= 4, care are mereu solutie.
Pentru a implementa acest algoritm se poate folosi o coada pentru a retine nodurile cu grad 0 cu un vecin cu grad diferit de 0 si liste inlantuite pentru a retine vecinii fiecarui nod. De fiecare data cand se va elimina un varf din configuratie, se vor verifica vecinii lui sa se vada daca trebuie adaugati in coada si se va actiona corespunzator. De observat este ca pe parcurs, cand extragem un varf din coada se poate ca acesta sa isi fi pierdut proprietatea ca are un vecin cu grad nenul, dar acest lucru nu influenteaza complexitatea algoritmului deoarece de fiecare data cand eliminam un nod din configuratie o sa adaugam maxim doua noduri in coada.
Complexitatea algoritmului este O(N).

Steins;Gate

Se observa faptul ca o valoare V se va propaga dintr-un nod X intr-un nod Y dupa K pasi, daca exista cel putin un drum de lungime K intre cele 2 noduri.
Ramane de aflat pentru fiecare nod Y, care sunt nodurile X astfel incat sa existe drum de lungime K intre X si Y. Dintre toate aceste noduri, vom selecta desigur nodul cu valoarea cea mai mare.
Problema ramasa este una clasica. Este suficient sa luam matricea de adiacenta si sa o ridicam la puterea K. Elementul de pe linia i coloana j a matricei rezultat va reprezenta numarul de drumuri de lungime fix K intre i si j. Deoarece ne intereseaza doar daca exista drum sau nu, putem lucra modulo 2.

Complexitate: O(N^3 * log K)

Tembelizor

O prima observatie ce putea fi facuta este ca matricea nu trebuia mentinuta in forma data in enunt. Mai exact pentru fiecare 2 culori x si y cu x ≠ y tot ce conteaza este daca ele se regasesc sau nu in pixeli adiacenti in matrice.
Pentru simplificarea explicarii solutiei vom face doua notatii:

  • doua culori x ≠ y se numesc adiacente daca exista 2 pixeli adiacenti in matrice unul avand culoarea x si altul culoarea y.
  • pentru o alegere de culori de upgrade ale tembelizorului exista un conflict (x, y) cu x ≠ y daca $x si $ au aceeasi culoare si sunt si adiacenti.

Pentru 10 puncte

O solutie care fixa cu ce culori se upgrada tembelizorul (dintre cele C - 2 posibile) avea complexitate O(2C*C2) cu O(C2) memorie (pentru a mentine pentru fiecare doua culori daca au un conflict sau nu). Pentru fiecare din cele 2C-2 alegeri posibile trebuia doar verificat daca exista vreun conflict.

Pentru 20 de puncte

In general orice problema de minimizare/maximizare a unui sume alegand sau nu niste obiecte cu un anumit cost se poate rezolva cu greedy (exemplu: arbore partial de cost minim) sau cu programare dinamica (exemplu: ciclu hamilton de cost minim, problema rucsacului). La aceasta problema se putea folosi a doua metoda, anume:

  • dp[i] = costul minim de a upgrada tembelizorul doar cu culori de la 1 la i, upgradand neaparat cu culoarea i, astfel incat sa nu exista niciun conflict (x, y) cu x ≠ y si x,y ≤ i
    Starea de inceput este dp[1] = 0 intrucat televizorul vine din start cu culoarea 1, iar raspunsul cerut se afla in dp[C].

dp[i] este max(dp[j] + cost[i]) cu properitatea ca daca se cumpara culoarea j < i si nicio alta culoarea x cu j < x < i atunci nu se formeaza niciun conflict (u, v) cu j ≤ u, v ≤ i.
O implementare directa a acestei solutii ar avea complexitate O(C4) cu O(C2) memorie si v-ar garanta 20 de puncte.

Pentru 30 de puncte

Solutia de mai sus se putea rafina foarte usor pentru a obtine o complexitate mai buna de O(C4) folosing urmatoarea observatie: daca exista 3 culori x, y, z cu x < y < z si x adiacent atat cu y cat si cu z atunci oricand conflictul (x, z) apare intr-o alegere de culori de upgrade ale tembelizorului cu siguranta apare si conflictul (x, y).
De aici deducem ca pentru fiecare culoare x din cele C conteaza doar cel mai mare y < x astfel incat x si y sunt adiacenti. Asta se poate nota cu closestDown[x] si analog pentru y > x cu closestUp[x].

Acum pentru a verifica daca exista un conflict daca se cumpara culorile i si j in recurenta programarii dinamice se pot verifica doar 2 * (j - i + 1) de perechi de culori adiacente obtinandu-se astfel o complexitate de O(C3) cu O(C) memorie.

Pentru 40 de puncte

Pentru a obtine o complexitate mai bune se puteau precalcula inca 2 siruri:

  • right[i] = j maxim cu j ≥ i astfel incat sa nu existe nicio pereche de culori adiacente (x, y) cu i ≤ x, y ≤ j
  • left[i] = j minim cu j ≤ i analog

Acum dinamica dp poate fi rescrisa astfel:

  • dp[i] = max(dp[j] + cost[i] cu j < i si right[j] ≥ mid si left[i] < mid unde mid = [(i + j - 1) / 2] (prin [x] s-a notat partea intreaga a lui x)

Complexitatea acestei idei este O(C2) cu O(C) memorie si ar fi obtinut 40 de puncte. Cu mici optimizari se puteau obtine si 50 de puncte.

Pentru 100 de puncte

Idea solutiei de punctaj maxim este urmatoarea, dp[j] este util pentru a-l calcula pe dp[i] doar pentru i ≤ 2 * right[j] - j + 2. Analog dp[i] se poate calcula doar din j ≥ 2 * left[i] - i - 1. Se putea tine atunci un arbore de intervale de minim peste dp.

  • Calcului lui dp[i] este doar un query de minim peste intervalul (2 * left[i] - i - 1, i - 1)
  • Dupa, dp[i] se updata in arborele de intervale si se marca in 2 * right[i] - i + 3 ca dp[i] nu mai este util, echivalent cu un update in arborele de intervale pe pozitia lui i cu infinit.

Astfel complexitatea obtina era O(C log C) cu O(C) memorie.