Solutia problemei Permdist

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 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).