Solutii Concurs de incalzire 2020

Soluţia problemei Minmax

10 puncte (n^n)

Putem genera toate partiţiile şirului, apoi pentru fiecare partiţie să verificăm dacă suma obţinută pentru aceasta partiţie este mai mare decât răspunsul pentru numărul de subşiruri al acesteia.

20 de puncte (3^n*n)

Vom folosi o dinamică pe stări exponenţiale maxim[nr][configuratie]. configuratie_subsir reprezintă un număr al cărui biţi setaţi la 1 indică elementele care apar în oricare din primele nr subşiruri.
Recurenţa obţinută va fi:

  • dp[nr][configuratie] = max { dp[nr-1][configuratie^subsir]+dif[subsir] | subsir este o submască a numărului configuratie }
  • dif[subsir] reprezintă diferenţa între maxim şi minim în subşirul subsir.

Cu precalculări pentru valorile dif, putem ajunge la o soluţie în O(n* 3^n).

40 de puncte (n^2)

Observăm următoarea relaţie:
suma {max(subsir)-min(subsir)| subsir e in partitie} = suma {max(subsir)| subsir e in partitie} - suma {min(subsir)| subsir e in partitie}
Cu alte cuvinte, cele 2 componente sunt independente şi pot fi calculate separat. Putem mereu sa luam aceste elemente, iar cele ce se afla intre ele sa le punem intr-un subsir arbitrar, deoarece nu influenteaza raspunsul.
Astfel, problema se reduce la a găsi suma maxima a k elemente din subşir şi a scădea din ea suma minimă a k elemente din subşir pentru un k fixat. Putem găsi aceste valori cu programare dinamică
( max[poz][cate] - suma maximă până la poziţia poz cu cate elemente, analog şi pentru minim, min[poz][cate]). Recurenţa nu este foarte dificilă şi o recomandăm ca exerciţiu.

100 de puncte (n * log n)

Facem urmatoarea observatie: cele mai mari k valori din sir sunt ultimele k in sir dupa sortare, iar cele mai mici primele k dupa sortare.
Acum problema se reduce la a calcula niste sume pe prefixul, respectiv sufixul unui sir, problema ce poate fi rezolvata in O(n) cu sume partiale, sau prin calculare explicita deoarece 2 raspunsuri consecutive difera doar prin 2 elemente adaugate.

Soluţia problemei Teste

20 de puncte (O(n^k)+O(sqrt(S)))

Generăm toate şirurile cu proprietaţile cerute folosind backtracking, adunăm toate elementele la S şi numărăm divizorii lui S în O(sqrt(S))

40 de puncte (O(n3)+O(sqrt(S)), O(n2)+O(sqrt(S)), O(n)+O(sqrt(S)))

La această grupă, putem în continuare să calculam explicit divizorii lui S, dar trebuie să găsim o metodă mai rapidă de a găsi suma S. O metoda poate fi programarea dinamică, calculând sum(l)(val) - suma tuturor elementelor şirurilor de lungime l cu ultimul element egal cu val şi nr(l)(val) -numărul de şiruri de lungime l cu ultimul element egal cu val. Recurenţa va fi:

  • sum(l)(val)=suma(sum(l-1)(i),i=1..n)+suma(nr(l-1)(i)+i=1..n)*val)
  • nr(l)(val)=nr(l-1)(val)

S va fi egal cu suma din $sum(n)(i) 1<=i<=n$$.
Această dinamică poate fi optimizată obţinând diverse complexităţi, dar forma de mai sus este suficientă pentru a obţine 40 de puncte.

100 de puncte O(sqrt(n)+sqrt(k))

Pentru a reuşi să obţinem un algoritm a cărui complexitate nu depinde de S, trebuie să exprimăm S într-un mod mai simplu. Pentru a găsi o soluţie începem prin a fixa o valoare pe o poziţie şi a vedea în câte şiruri apare, la S adăugandu-se produsul între valoare şi număr de apariţii. Dacă fixăm numărul de pe poziţia poz ca fiind val, şirul
va arăta astfel:
Pozitie |1 2.. poz ... n|
Valoare |? ?.. val ... ?|
Observam ca numarul de siruri in care val apare pe pozitia poz este numarul de moduri de a inlocui n-1 caractere ? cu numere de la 1 pana la k. Acest numar este egal cu k(n-1). Daca fixam doar pozitia poz si facem suma pentru toate numerele val de la 1 la k, vom obitne k(n-1)*k*(k+1)/2. Deoarece expresia este aceeasi indiferent oricare din cele n pozitii va fi poz, S va fi n*(k^(n-1)*k*(k+1)/2).
Observăm ca în formula anterioara apar doar puteri ale lui n, k şi k+1 (şi 2, pe care trebuie să îl reducem de unde este posibil), deci putem precalcula factorii primi ai acestora, şi observând la ce puteri apar cele 3 numere în formula pentru S, putem obţine factorizarea lui S "combinând" cele 3 factorizări. Răspunsul va fi produsul puterilor (la care se adauga 1) la care apar factorii primi ai lui S în factorizarea lui.

Soluţia problemei Ordonare

10 puncte O(n^n)

Putem, folosind bactracking, sa generam toate mutarile intr-o vecinatate a punctelor (-3-n, 3+n) poate fi suficient tinand cont ca numerele sunt in intervalul (-3,3).

20-30 de puncte O(n^4)

Putem incerca sa alegem configuratia optima a punctelor folosind cuplaj maxim de cost minim.
Vom cupla obiectele cu puncte din intervalul (xmin-n,xmin+n) (se poate observa ca acest interval este suficient) cu un cost egal cu lungimea segmentului dintre pozitia initiala si cea finala)

40 de puncte O(n*valmax)

Solutia de 40 este bazata pe urmatoarea observatie: daca sortam punctele, nu vom avea niciodata 2 puncte i,j pentru care x(i)<x(j) sa ajunga in solutia finala la coordonate x'(i)>x'(j) (nu ar aduce niciun beneficiu sa le schimbam ordinea relativa). Prin urmare, daca sortam punctele, acestea vor trebui ca in final sa formeze un sir strict crescator, obtinut cu operatiile enumerate.
Stiind ca punctele vor fi in intervalul (xmin-n,xmin+n) in final, putem sa facem o dinamica dp[i][j] avand urmatoarea semnificatie: am procesat primele i puncte in ordinea sortata, iar ultimul din ele se afla la coordonata cel mult egala cu j. Recurenta va fi:

  • dp[i][j]=min{dp[i-1][j-1]+|x[i]-j|,dp[i][j-1]}

60 de puncte O(n*n)

Putem optimiza solutia de 40, cu urmatoarea observatie: punctul i va ajunge in final in intervalul (x(i)-(n+1)/2),x(i)+(n+1)/2), deci putem sa adaptam dinamica de la solutia anterioara, folosind pentru fiecare punct doar coordonatele relevante. (si modificand usor recurenta, deoarece intervalele pentru 2 puncte consecutive nu vor corespunde neaparat)

O alta solutie se bazeaza pe urmatoarea observatie: avand sirul sortat de puncte, trebuie sa il transformam intr-un sir strict crescator. Acest lucru se poate realiza prin transformarea in urmatoarea problema:

Sa se transforme sirul v(i)=x'(i)-i intr-un sir (nu neaparat strict) crescator, unde x' este x sortat.

Aceasta problema se poate rezolva cu urmatoarea dinamica ( se observa ca doar coordonatele din sirul v sunt relevante ca pozitii finale):
dp(i)(j)- am transformat elementul i, in al j-lea element in ordine sortata din sirul v. (Recurenta este asemanatoare cu cea de la solutia de 40)

100 de puncte O(nlogn)

A doua solutie de mai sus, avand o forma mai simpla, poate fi optimizata. Acest lucru poate fi facut cu slope trick

Nota: A mai fost facuta publica o explicare a slope trick-ului

Soluţia problemei Pensula

Atunci cand arborele este un lant cu radacina intr-unul din capete, fiecare culoare (ignorand pentru o clipa faptul ca o culoare poate fi folosita de mai multe ori) ocupa un interval continuu de noduri. La fiecare operatie, un prefix al sirului de noduri este recolorat. Cu alte cuvinte, cateva intervale de la inceput dispar, altul este scurtat, iar cel nou este adaugat, fiind primul interval de la stanga la dreapta. Daca privim felul in care evolueaza sirul de capete drepata ale acestor intervale, observam ca operatiile sunt acelea suportate de stiva. Atunci cand stergem un interval, gradul de zapaceala al fiecarui nod din intervalul respectiv creste cu aceeasi valoare, xor-ul dintre culoarea intervalului si cea noua. Deoarece vrem sa aflam aceste valori numai la final, putem folosi smenul lui Mars. Aceasta solutie are complexitatea O(N + Q). Mai mentionam si ca sirul res se poate calcula pe long long, fara a fi nevoie de calcul modulo MOD pana la afisare.

Pentru restul punctelor, vom descompune arborele in lanturi. Culorile fiecarui lant in parte se comporta asemanator cu descrierea de mai sus, singura diferenta fiind aceea ca nu numai operatiile care recoloreaza direct un nod apartinand lantului afecteaza intervalele, ci si acelea care modifica orice nod din subarborii acestora. Fiecare operatie aplicata unui anumit nod va afecta exact acele lanturi pe care le intersecteaza drumul de la el la radacina. O descompunere eficienta in acest caz este aceea in care, atunci cand ne punem intrebarea, cu care dintre fiii unui anumit nod sa-i continuam lantul, il alegem pe acela cu cele mai multe noduri. Astfel, numarul de lanturi pe drumul de la un nod la radacina este O(logN), iar complexitatea solutiei de 100 de puncte este O(N + Q logN).

Se merita sa analizam si doua solutii care pot obtine 80 de puncte. Una dintre ele trateaza lanturile ca inainte, doar ca foloseste o alta descompunere in lanturi. In loc sa extindem lantul curent cu nodul al carui subarbore are cele mai multe noduri, il alegem pe acela pentru care inaltimea maxima din subarbore e cat mai mare. Astfel, numarul de lanturi de pe drumul de la un nod la radacina este O(sqrt(N)) iar complexitatea solutiei este O(N + Q sqrt(N)).

Cealalta solutie de 80 de puncte foloseste descompunerea optima, doar ca nu trateaza in timp liniar un lant. In schimb, vom construi un arbore de intervale ale carui noduri sunt exclusiv de tip "lazy", pe care le vom propaga la fiecare atingere a unui nod. In fiecare nod, vom retine trei numere despre intervalul curent: a = prima (cronologic) culoare care nu a fost impinsa in subintervale, b = ultima (cronologic) culoare care nu a fost impinsa in subintervale, si s = suma xor-urilor perechilor de culori consecutive care s-au acumulat intre a si b. Observatia e ca atunci cand propagam o informatie dintr-un nod in altul, stim ca toate culorile impinse au aparut ulterior (cronologic) (mai mult: imediat dupa) culorilor din intervalul mai mic. Prin urmare, atunci cand propagam aceasta informatie intr-un subinterval, adunam interval.s + (subinterval.b ^ interval.a) la subinterval.s si modificam subinterval.b in interval.b. Solutia are complexitatea O(N + Q logN logN).