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 d_T(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, d_T(x, y) = -1.
Să descompunem cele două permutări în cicluri.
Observaţie⁽¹⁾: î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⁽²⁾: 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_A_x pentru permutarea A, respectiv D_B_x pentru permutarea B, iar cu L_A_x şi L_B_x 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_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 fiecărei valori câte un coeficient C_x = (D_A_x - D_B_x) 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. 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 frecvenţa pentru calcularea numărului de valori y care au C_y = 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 ⁽²⁾, 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_A_x < D_A_y, D_B_x < D_B_y, şi restul de combinaţii de semne), astfel încât ecuaţia de la ⁽²⁾ 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 I_a. Să punem un marker într-un vector paralel cu Cycle(B) pe poziţia I_a - d_A(r, a) pentru fiecare a. Este clar că numărul de markere de pe poziţia I_r include un mare număr de elemente din soluţia noastră. Singură problema vine de la valorile u care au I_u < I_r, $I_u + D_B_u - d_A(r, u} = I_r ⁽³⁾ (Î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 Cycle²(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 d_A(r, a) poziţii înapoi relativ de fiecare apariţie a acesteia din Cycle²(B). Acum, este clar că existenţa problematică a unui u menţionat anterior este reparată de apariţia acestuia la cele D_B_u unităţi mai în faţă în şir (într-atât că ⁽³⁾ 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⁽⁴⁾ 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ă d_A(r,a) ≥ d_A(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 d_A(r', r) poziţii în urmă
2. Toate celelalte markere se duc cu d_A(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)

⁽⁴⁾: Aceasta este o afirmaţie falsă, deoarece dacă luăm un element arbitrar din mulţimea S şi avem D_A_a > D_B_a, 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, I_u + D_B_u ≥ I_r (vezi ⁽³⁾). 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 Cycle²(T), unde T este A dacă D_A_a > D_B_a (pentru un a din S), şi B dacă nu (aşa cum a fost descris pe parcursul acestui articol).