h1. 'Soluţia':jc2023/solutii/permdist problemei 'Permdist':problema/permdist
 

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

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.

h2. 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^({$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_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 ^({$2$})^ 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)$

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^({$1$})^: 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^({$2$})^: 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 ^({$2$})^ 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 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_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 ^({$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.

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 ^({$2$})^, 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 ^({$2$})^ 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.

h2. 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~}$ ^({$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 $Cycle^2^(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^2^(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ă ^({$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ă $d{~A~}(r,a) &geq; 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:

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~}$ ^({$3$})^ (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^2^(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^2^(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 ^({$3$})^ 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^({$4$})^ 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) &geq; 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:

# Markerele care proveneau de la valoarea $r$ se duc cu $d{~A~}(r', r)$ poziţii în urmă
# Toate celelalte markere se duc cu $d{~A~}(r, r')$ poziţii în faţă.

# Markerele care proveneau de la valoarea $r$ se duc cu $d{~A~}(r', r)$ pozitii in urma
# Toate celelalte markere se duc cu $d{~A~}(r, r')$ pozitii in fata.

Pentru a putea acomoda aceste operaţii, putem folosi trucul detaliat mai atent "aici":https://codeforces.com/blog/entry/58316 (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)

Pentru a putea acomoda aceste operatii, putem folosi trucul detaliat mai atent "aici":https://codeforces.com/blog/entry/58316 (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)

^({$4$})^: 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 ^({$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 $Cycle^2^(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).

^({$4$})^: 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 ^({$3$})^), 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^2^(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).