Solutii Algoritmiada 2011, Runda 1

• Lista de probleme
• Fsb
• Secvdist
• Doi
• Perioada
• TractoMarm

Fsb

Vom asocia fiecărei cifre 0 valoarea 1, iar fiecărei cifre 1 valoarea -1. În orice subsecvenţă în care numărul de cifre 0 este egal cu numărul de cifre 1, suma valorilor asociate elementelor va fi egală cu 0.

O primă idee ar fi de a determina toate subsecvenţele şi de a calcula pentru fiecare subsecvenţă suma valorilor elementelor (se contorizează fiecare subsecvenţă cu suma 0). Această abordare are complexitatea O(N³).

O primă optimizare se poate face observând că pentru a calcula suma valorilor pentru subsecvenţa i..j putem utiliza suma valorilor pentru subsecvenţa i .. (j - 1). Utilizând această observaţie obţinem un algoritm cu complexitatea O(N²).

Să notăm cu S(i, j) suma valorilor asociate elementelor din subsecvenţa care începe pe poziţia i şi se termină pe poziţia j.
Se observă că S(i, j) = S(1, i) - S(1, j - 1), 1 < i < j.

Deci pentru a determina sumele tuturor subsecvenţelor nu sunt necesare decât sumele pentru subsecvenţele de forma 1..i (care se pot calcula în O(N)).

Să notăm cu sol(x) = numărul de subsecvenţe de forma 1..i pentru care S(1, i) = x .
Subsecvenţele cu S(i, j) = 0 se obţin din perechi (i, j) pentru care S(1, i) = S(1, j - 1). Să notăm valoarea comună cu x. Suma x se obţine de sol(x) ori. Evident există sol(x) * (sol(x) - 1) / 2 perechi distincte de indici cu suma x. 

Rezultatul se obţine însumând pentru fiecare x sol(x) * (sol(x) - 1) / 2.

Secvdist

Problema se rezolva cu ajutorul a doua deque-uri. Tinem un deque pentru valoarea maxima, si unul pentru valoarea minima. Parcurgand sirul cu doi indici i,j cu j<=i
verificam la fiecare pas i daca diferenta dintre valoarea maxima si cea minima este mai mare decat K, moment in care incrementam indicele j si, daca este necesar, scoatem din deque valorile care nu se afla in secventa intre indicii i si j.

Complexitate: O(n).

Doi

Solutia 1 : Se foloseste o strategie de tip greedy.

• Daca numarul curent este par, cea mai eficienta operatie este impartirea cu 2.
• Daca numarul e impar - este de forma 2 * K + 1 - atunci avem urmatoarele doua cazuri :
  • (2 * K) / 2 = K este par. Adica daca scadem numarul nostru curent si il impartim cu 2 obtinem un numar par.
  • (2 * K + 2) / 2 = K + 1 este par. Adica daca crestem numarul nostru curent si il impartim cu 2 obtinem un numar par.

Astfel numarul se reduce pana cand devine nul, moment in care se afiseaza solutia.

Solutia 2 :

• Daca numarul curent este par, atunci il impartim la 2.
• Daca restul numarului curent la 4 este 1 sau numarul este 3, atunci scadem o unitate.
• Daca restul numarului curent la 4 este 3 atunci adunam o unitate.

Perioada

Cheia acestei probleme este a verifica rapid daca p este perioada a subsecventei x ... y, unde p divide y - x + 1. Ne vom folosi de operatia Lcp. Transformand problema intr-una un pic mai generala, vom calcula intai pentru pozitia x numarul maxim de perioade (x ... x + p - 1) pe care le putem suprapune peste sir, incepand de la x. Demonstram ca acest numar, fie el numit k, este Lcp(x, x + p) / p + 1.

Studiem forma subsecventelor care incep cu x si x + p.

x: ...... (P) (P) (P) (P) (P) ... (P) (P) || ...
x + p: ...... (P) (P) (P) (P) ... (P) (P) || ...

Este evident ca Lcp(x, x + p) va fi cel putin tot sirul de jos, adica (k - 1) * P. Pe de alta parte, nu poate fi mai mare sau egal cu ((k - 1) * p) + p = k * p, deoarece alfel s-ar crea o noua perioada, care ar fi fost si ea numarata de Lcp. (k - 1) * p <= Lcp(x, x + p) < k * p, deci k - 1 <= Lcp(x, x + p) / p < k. Acest lucru inseamna ca k este chiar Lcp(x, x + p) / p + 1.

Devine clar, deci, faptul ca p este perioada a subsecventei (x ... y) daca si numai daca (y - x + 1) / p <= k, echivalent cu (y - x + 1) / p <= Lcp(x, x + p) / p + 1. Practic, comparam numarul de perioade necesare acoperirii subsecventei cu numarul maxim de perioade de care dispunem.

Acum, putem ataca direct problema. Vom constui un Suffix Array pe sirul dat, pentru a folosi operatia Lcp. Pentru fiecare query, cu x si y aferente, vom considera pe rand toti divizorii lui (y - x + 1), testandu-i cu metoda descrisa mai sus. Trebuie sa fim atenti la cazuri particulare, mai ales cand p = (y - x + 1) si atunci cand (y - x + 1) este patrat perfect. Cum numarul divizorilor unui numar N este de ordinul sqrt(N), obtinem o complexitate totala de O(N * log^2(N) + sqrt(N) * log(N) * M), ceea ce totusi este putin prea mare. Aici se pot aplica doua optimizari, oricare dintre ele dovedindu-se suficiente pentru 100 de puncte:

Optimizare 1:

Observam ca Lcp(x, y) cu x si y indici in sirul sortat al sufixelor, este egal cu min(Lcp(x, x + 1), Lcp(x + 1, x + 2), ... Lcp(y - 1, y)). Vom retine pentru fiecare sufix al sirului pozitia sa in sirul sortat si vom construi in timp O(NlogN) un RMQ pe vectorul Lcp - urilor consecutive. O operatie Lcp s-a transformat intr-un query in RMQ, care se poate rezolva in O(1).

Optimizare 2:

Vom construi Suffix Array in timp O(NlogN) folosind o tehnica de sortare precum Radix sort.

TractoMarm

Solutie O(N + M)

Calculam distantele de la nodul 1 la celelalte noduri si notam suma lor cu S. Pentru un query (x, y) presupunem ca D[x] > D[y] (daca e invers interschimbam x cu y).
Daca D[y] + 1 = D[x] atunci distanta minima pana la x ramane aceeasi, deci suma distantelor ramane neschimbata.
Daca D[y] + 1 < D[x] atunci distanta minima pana la x se miscoreaza cu V = D[x] - D[y] - 1.
Observam ca toate nodurile din subarborele cu radacina x vor avea noua distanta minima cu V mai mica decat cea veche. Insa, exista posibilitatea ca si tatal lui x sa aiba noua distanta minima mai mica decat cea veche (si implicit fiii lui) si tatal tatalui si tot asa.
Notam cu DNOU[i] distanta minima noua de la nodul 1 pana la nodul i si cu T[i] tatal nodului i.
Stim ca DNOU[x] = D[x] - V si ca D[T[x]] + 1 = D[x]. De aici rezulta ca DNOU[T[x]] = DNOU[x] + 1 = D[x] - V + 1 = D[T[x]] - V + 2. Deci DNOU[T[x]] = D[T[x]] - (V - 2). Asta inseamna ca tatalui lui x si a fiilor acestuia li s-a imbunatatit distanta cu V - 2. Continuand rationamentul DNOU[T[T[x]]] = D[T[T[x]]] - (V - 4) si tot asa pana cand nu se mai imbunatateste distanta.

Notam cu subFara[i] numarul nodurilor din subarborele cu radacina i, fara nodurile din subarborele din care am venit si cu subArb[i] tot subarborele. De asemenea T^k[x] va reprezenta al k-lea stramos al lui x (T⁰[x] = x).
Atunci suma a distantelor se va miscora cu S2 = V * subFara[x] + (V - 2) * subFara[T[x]] + (V - 4) * subFara[T[T[x]]] + ...

Avem doua cazuri:
C1) V este par, deci V = 2 * k. Inlocuind in formula de mai sus ne da
S2 = 2k subFara[x] + 2(k - 1) subFara[T[x]] + 2(k - 2) subFara[T[T[x]]] + ... + 2 subFara[T^k-1[x]] =
= 2 (k subArb[x] + (k - 1) subFara[T[x]] + (k - 2) subFara[T[T[x]]] + ... + subFara[T^k-1[x]]) =
= 2 (subArb[x] + (k - 1) subArb[x] + (k - 1) subFara[T[x]] + (k - 2) subFara[T[T[x]]] + ... ) =
= 2 (subArb[x] + (k - 1) (subArb[x] + subFara[T[x]]) + (k - 2) subFara[T[T[x]]] + ... ) =
= 2 (subArb[x] + (k - 1) subArb[T[x]] + (k - 2) subFara[T[T[x]]] + ... ) =
= ... = 2 (subArb[x] + subArb[T[x]] + ... + subArb[T^k-1[x]]).

C2) V este impar, deci V = 2 * k + 1. Similar obtinem
S2 = 2 (subArb[x] + subArb[T[x]] + ... + subArb[T^k-1[x]]) + subArb[T^k[x]].

Pentru a calcula rapid aceste sume trebuie sa precalculam toti stramosii de care avem nevoie in O(N + M) ca si la problema Cerere precum si sume partiale pentru subArb.