• Lista de probleme
• Omida Mincinoasa
• Salutare Jupane
• Permdist

Soluţia problemei Omida Mincinoasa

Pentru început, observăm că C(n,i)·i^k înseamnă de fapt să alegem un subşir de lungime i a mulţimii {1,2,3,...,n}, şi după aceea să alegem o tuplă de lungime k din subşirul respectiv. În acest fel, numărăm toate perechile de tipul (subşir, tuplă), dar acest lucru este echivalent cu a număra perechi de tipul (tuplă, subşir). Observăm în continuare că pentru a alege un subşir care acoperă o tuplă de valori depinde doar de numărul de valori distincte x din tuplă, iar numărul de moduri să alegem subşirul este 2^n-x. Astfel, dacă vom găsi un mod prin care să calculăm numărul de tuple cu x valori distincte, am rezolvat problema.

Subtask 6: k ≤ 500

Putem folosi următoarea dinamică pentru a număra tuple: dp[i][j] = numărul de tuple de lungime i care conţin toate valorile din [1,j]. Ca recurenţă, să spunem că tupla noastră conţine k > 1 valori egale cu j, atunci dp[i][j] += dp[i-k][j-1]·C(i,k).

Prin urmare, am rezolvat acest subtask în O(k³).

O implementare bazată pe această idee poate fi văzută aici.

Subtask 7: k ≤ 5000

Observăm că dinamica de mai sus numără funcţii surjective definite pe {1,2,3,...,k} cu valori în {1,2,3,...,j}. Numărarea acestor funcţii este un lucru cunoscut, o putem face prin diverse metode, soluţia oficială se foloseşte de numere Stirling de speta a 2-a, cu o complexitate finală de O(maxk² + t·k).

O implementare bazată pe această idee poate fi văzută aici.

Soluţia problemei Salutare Jupâne

Vom încerca să tratăm suma independent pe fiecare prefix al descompunerii. Astfel, vom fixa prefixul de lungime t şi vom calcula suma din gcd(a{1}, a{2}, ..., a{t}) pentru toate descompunerile lui n.

Solutie in O(m·nrdiv·log)

Este cunoscut că suma din phi(i) pentru toţi divizorii lui n este chiar n, unde phi(i) reprezintă numărul de numere prime cu i mai mici decât i. Astfel, în loc să calculăm suma din gcd, vom calcula suma din phi(x) cu x | gcd.

Să fixăm x şi să numărăm câte descompuneri ale lui n au k termeni şi prefixul de lungime t are gcd-ul multiplu de x. Singura condiţie impusă este că primii t termeni din descompunere să fie multipli de x, deci trebuie să numărăm descompunerile lui n/x^t în k termeni, lucru care poate fi făcut cu uşurinţă considerând fiecare factor prim independent şi înmulţind răspunsurile. Dacă un factor prim are exponent e, atunci avem nevoie de numărul de soluţii ale b{1} + b{2} + ... + b{k} = e, deci vom folosi stars and bars.

Pentru a obţine complexitatea din subtitlu, folosim memoizare pentru a nu calcula descompunerile de mai multe ori decât este necesar şi observăm că pentru orice x > 1, acesta poate contribui doar în log prefixe.

Solutie in O(m·log²)

Vom schimba modul în care calculăm răspunsul pentru un prefix. Să presupunem că n=p₁^e₁·p₂^e₂·...·p_l^e_l. Vom folosi dp[i] = suma tuturor gcd-urilor considerând doar primii i factori primi. Observăm că dp[i] = dp[i-1]·(suma tuturor gcd-urilor când considerăm doar factorul prim curent), întrucât orice gcd care poate fi obţinut doar cu factorul prim curent poate fi cuplat cu orice gcd vechi, deci în final doar înmulţim răspunsurile pentru fiecare factor prim separat. Acum putem folosi soluţia de dinainte, doar că nu mai trebuie să considerăm toţi divizorii, ci doar cei care sunt puteri ale unui număr prim, în total log astfel de numere.

Subtaskurile 1-3, 20 puncte

Putem, pentru fiecare zi, lista birourile vizitate de cei doi in acea zi in doi vectori diferiti. Raspunsul este numarul de pozitii unde valorile coincid in cei doi vectori.

Subtaskul 4, 36 puncte

Notam cu d_T(x, y) (distanta in T de la x la y) ca numarul de ori necesar de a aplica x = T[x] pana cand x devine egal cu y. Daca asta este imposibil, d_T(x, y) = -1.
Sa descompunem cele doua permutari in cicluri.
Observatie⁽¹⁾: in ziua x, cei doi se vor intalni in y daca si numai daca x si y apartin aceluiasi ciclu si in A, si in B.
Reformulare⁽²⁾: Daca in fiecare ciclu am desemna un reprezentant (aleator), iar pentru fiecare valoare x din ciclul respectiv am nota distanta acestuia de la reprezentant cu D_A_x pentru permutarea A, respectiv D_B_x pentru permutarea B, iar cu L_A_x si L_B_x lungimea ciclului caruia apartine x in A, respectiv in B, atunci in ziua x cei doi se vad in y daca si numai daca apartin aceluiasi ciclu in ambele permutari, si (D_A_y - D_A_x) mod L_A_x = (D_B_y - D_B_x) mod L_B_x
Cum pentru toate numerele L_A_x = L_B_x = N, putem asocia fiecarei valori cate un coeficient C_x = (D_A_x - D_B_x) mod N. Pentru fiecare x, numarul de y unde cei doi se vor intalni este egal cu numarul de valori y a.i. C_x = C_y cum (D_A_x - D_B_x) mod N = (D_A_y - D_B_y) mod N <=> (D_A_y - D_A_x) mod N = (D_B_y - D_B_x) mod N, iar din din ⁽²⁾ aceasta este corect. Se poate utiliza un vector de frecventa pentru calcularea numarului de valori y care au C_y = C, C fiind variabil dupa x. Complexitate timp (si memorie): O(N)

Motivul pentru care o asemenea solutie nu functioneaza pe cazul general este datorit inabilitatii de a pune valorile care depind de x respectiv y de aceeasi parte a parantezei asa cum este formulat in ⁽²⁾, cum cele doua parti ale egalitatii se pot afla sub modulo-uri diferite. Incercari de a lucra peste multimea valorilor y care sunt in acelasi ciclu ca x si pentru care se fixeaza o ierarhie intre valorile din diferente (adica y sa respecte ca D_A_x < D_A_y, D_B_x < D_B_y, si restul de combinatii de semne), astfel incat ecuatia de la ⁽²⁾ sa aibe ambele parti ale egalitatii ca ecuatii in Z pot duce la o solutie in O(N * log(N)) care ar putea trece pe Subtaskul 5.

Subtaskul 6, 100 puncte

Sa grupam valorile dupa ce cicluri apartin in cele doua permutari, si sa luam o multime de astfel de numere, S (care apartin aceluiasi ciclu in ambele permutari). Fie Cycle(T) un sir astfel incat scrierea fiecarui ciclu din % ca elemente consecutive din acesta este o subsecventa din Cycle(A). Exemplu: pentru T = [5, 3, 2, 1, 4], Cycle(T) poate fi egal si cu [5, 4, 1, 3, 2], si cu [2, 3, 1, 5, 4]. Nu conteaza valoarea efectiva atata timp cat se pastreaza proprietatea mentinuta anterior. Fie o valoare r pentru care vrem sa calculam raspunsul. Pentru fiecare valoare a, din S, sa consideram pozitia acesteia din Cycle(B), ca I_a. Sa punem un marker intr-un vector paralel cu Cycle(B) pe pozitia I_a - d_A(r, a) pentru fiecare a. Este clar ca numarul de marke