Soluţia problemei Gcdseq

Gcdseq

O(N3) - 10 puncte

În acest subtask putem lua fiecare subsecvenţă posibilă şi să calculăm maximul în O(N). La sfârşit calculăm cel mai mare divizor comun al lungimii şi al maximului folosind algoritmul lui Euclid şi să adăugăm la sumă.

O(N2*logVALMAX^) - 30 de puncte

În acest subtask, putem calcula pentru fiecare subsecvenţă maximul într-un mod mai eficient. Fixându-ne capătul din stânga, putem itera cu capătul din dreapta până la sfârşitul şirului şi să reţinem valoarea maximă. La sfârşit, calculăm cel mai mare divizor comun ca şi în soluţia anterioară. Factorul de logVALMAX intervine din cauza algorimului lui Euclid. În soluţia anterioară, acest factor nu apare, deoarece folosim algoritmul de cel mai mare divizor comun doar de N2 ori.

O(N*cbrt(VALMAX) + VALMAX*logVALMAX) - 100 de puncte

Pentru început, putem parcurge elementele în ordinea valorii, de la cel mai mic element, la cel mai mare element. Astfel, dacă ne aflăm la elementul i, ştim că acesta va fi cel mai mare element dintre cele deja parcurse. Folosind această intuiţie, soluţia noastră va arăta în felul următor:

  • Parcurgem elementele de la cel mai mic la cel mai mare.
  • Când ne aflăm la elementul i, adăugăm la suma finală valorile subsecvenţelor cu elemente deja parcurse care îl conţin şi pe i.

Observaţie: vorbim despre elementele deja parcurse şi nu elemente mai mici sau egale, pentru a ţine cont de cazul în care avem elemente egale. Practic, dacă două elemente sunt egale ca valoare, nu trebuie să le tratăm special, doar le vom parcurge în orice ordine şi vom face acelaşi lucru ca şi la elementele distincte.

O altă observaţie importantă este că odată ce am parcurs un element, nu ne mai pasă de valoarea lui, deoarece nu va mai fi maxim. Practic, atunci când suntem la elementul i, ne pasă câte elemente din stânga lui (care să formeze o bucată contiguă) există şi acelaşi lucru pe partea dreaptă. Pentru a menţine astfel de informaţii, putem folosi păduri de mulţimi disjuncte, sau liste dublu-înlănţuite, deoarece atunci când parcurgem un element, practic îl unim cu intervalul din stânga lui şi cel din dreapta lui pentru a forma un nou interval compact.

Aşadar, trebuie să implementăm funcţia union(L, i, R), care înseamnă că unim un interval de lungime L cu un interval de lungime R şi cu elementul de pe poziţia i şi să vedem cum se schimbă suma. Putem să iterăm prin toate gcd-urile posibile dintre maxim şi lungime. Cum maximul este fixat, ştim că acest gcd va fi un divizor al acestuia. Cum am fixat şi maximul, şi gcd-ul final, trebuie ţinut cumva cont şi de lungimile secvenţelor.

Aici intervine o problemă: toate lungimile posibile care să dea gcd-ul fixat sunt multiplii ai acestuia. Această afirmaţie nu funcţionează şi invers, astfel putem avea un multiplu al acelui gcd, iar cel mai mare divizor comun dintre lungime şi maxim să dea diferit. Acest lucru nu ne încurcă aşa tare, deoarece am putea folosi la sfârşit o soluţie bazată pe Principiul Includerii şi Excluderii pentru a afla rezultatele pe care le voiam iniţial.

Astfel, în implementarea funcţiei de union, trebuie să calculăm pentru fiecare divizor al lui v[i] valoarea cnt[k] ce reprezintă câte subsecvenţe de lungime multiplu de k există care îl conţin pe elementul i şi sunt formate doar din elemente deja parcurse. Cum cunoaştem lungimile intervalelor vecine, acest lucru este uşor de calculat, acest număr de subsecvenţe fiind o formulă (care va fi prezentată mai încolo).

Singurul lucru rămas este să transformăm numerele calculate din "numărul de subsecvenţe care dau gcd-ul un multiplu de k", adică şirul cnt[k] în "numărul de subsecvenţe care dau gcd-ul exact k", fie acesta cnt2[k].

Dacă ne uităm mai bine, vom observa că valoarea cnt[v[i]] acoperă doar subsecvenţele care dau cel mai mare divizor comun egal cu v[i], în timp ce cnt1 acoperă toate subsecvenţele posibile, inclusiv pe cele care dau gcd-ul egal cu 2, 3, 4 sau alte valori.

Într-o manieră asemănătoare ca şi la începutul soluţiei, putem parcurge divizorii în ordine, de data aceasta descrescătoare şi să calculăm cnt2 pe parcurs. Putem observa că cnt[k] = cnt2[k] + cnt2[2 * k] + cnt2[3 * k] + ... + cnt2[T * k] pentru orice T. Cum suntem la o valoare k şi am calculat toate cnt2-urile pentru valori mai mari, putem calcula uşor cnt2[k], acesta fiind cnt[k] - cnt2[2 * k] - cnt2[3 * k] - ... - cnt[T * k].

În funcţie de cum implementăm calculul acestui şir cnt pentru fiecare operaţie de union, putem obţine multiple complexităţi şi să ajungem la complexităţi de forma O(N * T2), unde T este numărul maxim de divizori pe care îl poate avea un număr mai mic decât VALMAX, ceea ce nu este suficient.

Ultima observaţie necesară pentru a rezolva problema este că nu trebuie să calculăm cnt şi cnt2 pentru fiecare operaţie de union, ci putem calcula un şir cnt global pe care îl actualizăm la fiecare operaţie de union. Pe cnt2 îl calculăm tot global, după toate operaţiile de union, exact la fel ca şi în cazul în care calculam şirurile local. Singura diferenţă este în acest caz nu trebuie să lucrăm cu divizorii unui număr, în timp ce dacă le calculam local, trebuia pentru un divizor să parcurgem toţi multiplii lui care sunt tot divizori.

Formula

Fie funcţia cntMul3(L, R, k) = câte subsecvenţe de lungime multiplu de k există dacă am uni un interval de lungime L, un element x, un interval de lungime R şi acele subsecvenţe includ elementul x.

Pentru asta, putem folosi o funcţie ajutătoare: cntMul(N, k) = câte subsecvenţe de lungime multiplu de k există într-un şir de N elemente. Putem calcula asta în următorul mod:

  • Există N - k + 1 subsecvenţe de lungime k
  • Există N - 2k + 1 subsecvenţe de lungime 2k
  • ...
  • Există N - tk + 1 subsecvenţe de lungime tk, unde t este [N / k].

Însumând totul, obţinem:
cntMul(N, K) = N - k + 1 + N - 2k + 1 + ... + N - tk + 1
cntMul(N, K) = (N + 1) * t - k * (1 + 2 + 3 + ... + t)
cntMul(N, K) = (N + 1) * t - k * t * (t + 1) / 2
cntMul(N, K) = (N + 1) * [N / k] - k * [N / k] * ([N / k] + 1) / 2.

Folosind funcţia cntMul, putem calcula uşor funcţia cntMul3:
cntMul3(L, R, k) = cntMul(L + R + 1, k) - cntMul(L, k) - cntMul(R, k).

În această formulă, practic calculăm toate subsecvenţele posibile, din care scădem cele care nu conţin elementul x.

Astfel, în implementarea soluţiei vom avea mai multe componente:

  • Listele sau pădurea de mulţimi folosită pentru a menţine informaţii despre elemente deja parcurse în complexitate O(N) sau O(Nlog*)
  • Pentru a parcurge eficient divizorii unui număr, va trebui să precalculăm pentru fiecare număr un vector cu divizorii acestuia, lucru pe care îl putem face cu ciurul lui Eratostene în complexitate O(VALMAX + VALMAX/2 + VALMAX/3 + ... + VALMAX/VALMAX) ~ O(VALMAX * logVALMAX)
  • Pentru fiecare operaţie de union, parcurgem toţi divizorii unui număr, deci complexitatea va fi O(N * T) unde T este numărul maxim de divizori pe care îi are un număr mai mic sau egal cu VALMAX. O aproximare folosită frecvent pentru acest număr este cbrt(VALMAX), deci complexitatea va fi O(N * cbrt(VALMAX))
  • Calcularea şirului cnt2 de la final, care se face tot cu ciurul lui Eratostene modificat, în complexitate O(VALMAX * logVALMAX).

Combinând toate aceste componente, obţinem complexitatea finală de O(N * cbrt(VALMAX) + VALMAX * logVALMAX).