Solutia 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 aplică 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ţîn 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ţîn 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 ⁽²⁾ această 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 află 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ă aibe ambele părţi ale egalităţii că 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

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 T 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 markere de pe pozitia I_r include un mare numar de elemente din solutia noastra. Singura problema vine de la valorile u care au I_u < I_r, $I_u + D_B_u - d_A(r, u} = I_r ⁽³⁾ (In termeni mai familiari, u ar ajunge la r "prin spatele ciclului din B"). Pentru a repara aceasta, sugeram lucrarea pe un vector similar lui Cycle(B), dar care ar repara aceasta problema. Introducem notiunea sirului Cycle²(B), a carui definitie este similara, doar ca scrierea fiecarui ciclu (ca elemente consecutive din parcugerea acestora) este scrisa de doua ori (in aceeasi ordine de fiecare data). Exemplu: pentru T = [5, 3, 2, 1, 4], Cycle(T) poate fi egal si cu [5, 4, 1, 5, 4, 1, 3, 2, 3, 2], si cu [2, 3, 2, 3, 1, 5, 4, 1, 5, 4]. Din nou, nu conteaza cu care varianta lucram atata timp cat se pastreaza aceste propietati. Continuam cu notiunea markerelor, doar ca pentru fiecare valoare a din S, punem un marker cu d_A(r, a) pozitii inapoi relativ de fiecare aparitie a acesteia din Cycle²(B). Acum, este clar ca existenta problematica a unui u mentionat anterior este reparata de aparitia acestuia la cele D_B_u unitati mai in fata in sir (intr-atat ca ⁽³⁾ se respecta). Acum, structura data (a markerelor) ne poate raspunde corect la queryuri. Singura problema este ca aceasta este (in momentul de fata) descrisa cat sa poata sa raspunda corect⁽⁴⁾ doar la queryuri privind pe r. Trebuie sa reparam asta. Sa presupunem ca avem la indemana un r' care respecta ca pentru orice alt a in S, a != r, avem ca d_A(r,a) ≥ d_A(r, r'). Atunci, pozitiile markerelor se vor schimba (daca am vrem sa adaptam structura noastra de date la a raspunde la queryuri pentru r') asemenea:

1. Markerele care proveneau de la valoarea r se duc cu d_A(r', r) pozitii in urma
2. Toate celelalte markere se duc cu d_A(r, r') pozitii in fata.

Pentru a putea acomoda aceste operatii, putem folosi trucul detaliat mai atent aici (Un vector de frecventa pe care mentinem o variabila globala de lazy care indica cum trebuie sa modificam celelalte valori cu respect fata de operatiile de tipul 2)

⁽⁴⁾: Asta este fals, intr-atat ca daca (pentru a arbitrar din S) D_A_a > D_B_a, atunci nu este suficient concatenarea de doua ori a ciclurilor cand vrem sa reparam "ciclarea pe la spate", intr-atat ca acest truc a mers doar pentru ca am presupus ca pentru orice u, I_u + D_B_u ≥ I_r (vezi ⁽³⁾), intr-atat ca pentru a considera si cazul "ciclarii pe la spate" este necesara o singura parcurgere a acestui ciclu. Asta nu este adevarat daca putem avea valori ale d_A(r, u) mai mari decat D_B_u. De aceea, cand calculam raspunsul pentru o multime, vom pune markere intr-un vector paralel cu Cycle²(T), unde T este A daca D_A_a > D_B_a (pentru un a din S), si B daca nu (cum a fost descris de-a lungul acestui editorial).