Soluţii Algoritmiadă 2022, Runda 2

Soluţia problemei Drum8

Fie i indicele poziţiei la care am ajuns în vectorul A şi j indicele poziţiei la care am ajuns în vectorul B. O deplasare în jos este echivalentă cu a incrementa valoarea lui i, iar o deplasare la dreapta este echivalentă cu a incrementa valoarea lui j.

Cazul 1: 0 ≤ A[i], B[i] ≤ 1

Incrementăm valorile lui i şi j până când A[i] > 0 şi B[j] > 0. Acum incrementăm i până ajungem la ultima valoare egală cu 1 din vectorul A. Apoi incrementăm j până ajungem la ultima valoare egală cu 1 din vectorul B. După nu mai este relevantă ordinea în care incrementăm pointerii deoarece A[i] * B[j] = 0, deci nu contribuie cu nimic la sumă.

Cazul 2: 0 ≤ A[i], B[i] ≤ 2

Incrementăm valorile lui i şi j până când A[i] > 0 şi B[j] > 0. Fie x numărul de valori de 1 până la primul 2 din vectorul A şi y numărul de valori de 2 din vectorul B. Dacă x < y, incrementăm i până ajungem la primul 2, apoi incrementăm j până la ultimul 2 din vectorul B, iar apoi incrementăm iar i până la ultimul 2 din vectorul A. Pentru x > y, incrementăm în ordine inversă. Acum i şi j pointează spre ultimele valori egale cu 2 din A, respectiv B. Dacă numărul de valori egale cu 1 care au ramas în vectorul A este mai mare decât numărul de valori din vectorul B, incrementăm j până la ultima valoare egala cu 1, iar apoi i până la ultima valoare egală cu 1. Analog pentru celălalt caz. Apoi este irelevantă ordinea în care incrementăm pointerii, deci afişăm traseul minim lexicografic.

Soluţia problemei Matrice echilibrata

Observăm că suma elementelor matricei este suma = N * X = M * Y, altfel nu exista soluţie. Presupunem mai întai că X, Y sunt coprime. Fie p = cmmdc( N, M). Cum X şi Y sunt coprime rezultă că N * X = M * Y = cmmmc( N, M) = N * M / p. Deci X = M / $p, Y = N / p. Împărţim matricea în bucăţi de N / p pe M / p. Acum, fiecare rând trece prin M / ( M / p ) = p submatrici. Fiecare coloană trece prin N / ( N / p )) = p submatrici. Aşadar, ne putem imagina că avem o matrice de p × p elemente, fiecare element fiind defapt o submatrice de dimensiuni N / p × M / p = X × Y. Observăm că este suficient să completam toate elemenetele submatricilor de pe diagonala principală cu 1, şi aşa vom avea pe fiecare rând X elemente de 1 si pe fiecare coloană Y elemente de 1.

Presupunem acum ca gcd( X, Y) = q. Atunci N * X / q = M * Y / q = cmmmc( N , M) = N * M / p. Deci X= M * q / p şi Y = N * q / p. Cum X < M rezultă că q < p. La fel ca înainte deci putem împărţi în bucăţi de N / p pe M / p, şi luăm q diagonale "principale" şi le umplem cu 1-uri. Practic, pe fiecare linie completăm elementele primelor q submatrici cu 1. Atunci fiecare linie o să aibă M * q / p = X elemente, şi analog la coloane.

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).