Soluţia problemei Omida Mincinoasa

Pentru început, observăm că C(n,i)·ik î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 2n-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(k3).

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(maxk2 + 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·log2)

Vom schimba modul în care calculăm răspunsul pentru un prefix. Să presupunem că n=p1e1·p2e2·...·plel. 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.

Soluţia problemei Permdist

Subtaskurile 1-3, 20 puncte

Putem, pentru fiecare zi, lista birourile vizitate de cei doi în acea zi în doi vectori diferiţi. Răspunsul este numărul de poziţii unde valorile coincid în cei doi vectori.

Subtaskul 4, 36 puncte

Notăm cu dT(x, y) (distanţă în T de la x la y) că numărul de ori necesar de a aplica x = T[x] până când x devine egal cu y. Dacă asta este imposibil, dT(x, y) = -1.
Să descompunem cele două permutări în cicluri.
Observaţie(1): în ziua x, cei doi se vor întâlni în y dacă şi numai dacă x şi y aparţin aceluiaşi ciclu şi în A, şi în B.
Reformulare(2): Dacă în fiecare ciclu am desemna un reprezentant (aleator), iar pentru fiecare valoare x din ciclul respectiv am notă distanţă acestuia de la reprezentant cu D_Ax pentru permutarea A, respectiv D_Bx pentru permutarea B, iar cu L_Ax şi L_Bx lungimea ciclului căruia aparţine x în A, respectiv în B, atunci în ziua x cei doi se văd în y dacă şi numai dacă aparţin aceluiaşi ciclu în ambele permutări, şi (D_Ay - D_Ax) mod L_Ax = (D_By - D_Bx) mod L_Bx
Cum pentru toate numerele L_Ax = L_Bx = N, putem asocia fiecărei valori câte un coeficient Cx = (D_Ax - D_Bx) mod N. Pentru fiecare x, numărul de y unde cei doi se vor întâlni este egal cu numărul de valori y a.i. Cx = Cy cum (D_Ax - D_Bx) mod N = (D_Ay - D_By) mod N <=> (D_Ay - D_Ax) mod N = (D_By - D_Bx) mod N, iar din din (2) aceasta este corect. Se poate utiliza un vector de frecvenţa pentru calcularea numărului de valori y care au Cy = C, C fiind variabil după x. Complexitate timp (şi memorie): O(N)

Motivul pentru care o asemenea soluţie nu funcţionează pe cazul general este datorit inabilităţii de a pune valorile care depind de x respectiv y de aceeaşi parte a parantezei aşa cum este formulat în (2), cum cele două părţi ale egalităţii se pot afla sub modulo-uri diferite. Încercări de a lucra peste mulţimea valorilor y care sunt în acelaşi ciclu că x şi pentru care se fixează o ierarhie între valorile din diferenţe (adică y să respecte că D_Ax < D_Ay, D_Bx < D_By, şi restul de combinaţii de semne), astfel încât ecuaţia de la (2) să aibă ambele părţi ale egalităţii ca ecuaţii în Z pot duce la o soluţie în O(N * log(N)) care ar putea trece pe Subtaskul 5.

Subtaskul 6, 100 puncte

Să grupăm valorile după ce cicluri aparţin în cele două permutări, şi să luăm o mulţime de astfel de numere, S (care aparţin aceluiaşi ciclu în ambele permutări). Fie Cycle(T) un şir astfel încât scrierea fiecărui ciclu din T ca elemente consecutive din acesta este o subsecventă din Cycle(A). Exemplu: pentru T = [5, 3, 2, 1, 4], Cycle(T) poate fi egal şi cu [5, 4, 1, 3, 2], şi cu [2, 3, 1, 5, 4]. Nu contează valoarea efectivă atâta timp cât se păstrează proprietatea menţionată anterior. Fie o valoare r pentru care vrem să calculăm răspunsul. Pentru fiecare valoare a, din S, să considerăm poziţia acesteia din Cycle(B), ca Ia. Să punem un marker într-un vector paralel cu Cycle(B) pe poziţia Ia - dA(r, a) pentru fiecare a. Este clar că numărul de markere de pe poziţia Ir include un mare număr de elemente din soluţia noastră. Singură problema vine de la valorile u care au Iu < Ir, $Iu + D_Bu - dA(r, u} = Ir (3) (În termeni mai familiari, u ar ajunge la r "prin spatele ciclului din B"). Pentru a repara această, sugerăm lucrarea pe un vector similar lui Cycle(B), dar care ar repara această problema. Introducem noţiunea şirului Cycle2(B), a cărui definiţie este similară, doar că scrierea fiecărui ciclu (ca elemente consecutive din parcugerea acestora) este scrisă de două ori (în aceeaşi ordine de fiecare dată). Exemplu: pentru T = [5, 3, 2, 1, 4], Cycle(T) poate fi egal şi cu [5, 4, 1, 5, 4, 1, 3, 2, 3, 2], şi cu [2, 3, 2, 3, 1, 5, 4, 1, 5, 4]. Din nou, nu contează cu care varianta lucrăm atâta timp cât se păstrează aceste propietăţi. Continuăm cu noţiunea markerelor, doar că pentru fiecare valoare a din S, punem un marker cu dA(r, a) poziţii înapoi relativ de fiecare apariţie a acesteia din Cycle2(B). Acum, este clar că existenţa problematică a unui u menţionat anterior este reparată de apariţia acestuia la cele D_Bu unităţi mai în faţă în şir (într-atât că (3) se respectă). Acum, structura dată (a markerelor) ne poate răspunde corect la queryuri. Singură problema este că această este (în momentul de faţă) descrisă cât să poată să răspundă corect(4) doar la queryuri privind pe r. Trebuie să reparăm asta. Să presupunem că avem la îndemână un r' care respectă că pentru orice alt a în S, a != r, avem că dA(r,a) ≥ dA(r, r'). Atunci, poziţiile markerelor se vor schimbă (dacă am vrem să adaptăm structura noastră de date la a răspunde la queryuri pentru r') asemenea:

  1. Markerele care proveneau de la valoarea r se duc cu dA(r', r) poziţii în urmă
  2. Toate celelalte markere se duc cu dA(r, r') poziţii în faţă.

Pentru a putea acomoda aceste operaţii, putem folosi trucul detaliat mai atent aici (Un vector de frecvenţa pe care menţinem o variabilă globală de lazy care indică cum trebuie să modificăm celelalte valori cu respect faţă de operaţiile de tipul 2)

(4): Aceasta este o afirmaţie falsă, deoarece dacă luăm un element arbitrar din mulţimea S şi avem D_Aa > D_Ba, atunci nu este suficient să concatenăm de două ori ciclurile atunci când dorim să corectăm "ciclarea inversă". Faptul că acest truc a funcţionat a fost doar pentru că am presupus că pentru orice nod u, Iu + D_Bu ≥ Ir (vezi (3)). Acest lucru înseamnă că pentru a rezolva şi problema "ciclării inverse" este necesară doar o singură parcurgere a acestui ciclu. Totuşi, nu este adevărat dacă putem avea valori ale distanţei d{A}(r, u) mai mari decât D_B{u}. Prin urmare, atunci când calculăm răspunsul pentru o mulţime, vom adăuga marcaje într-un vector paralel cu Cycle2(T), unde T este A dacă D_Aa > D_Ba (pentru un a din S), şi B dacă nu (aşa cum a fost descris pe parcursul acestui articol).