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 aplică $x = T[x]$ până când $x$ devine egal cu $y$. Dacă asta este imposibil, $d{~T~}(x, y) = -1$.
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ţîn 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ţî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 ^({$2$})^ 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)$
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)$
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 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 ^({$2$})^ 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.
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.
h2. 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~}$ ^({$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) ≥ 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:
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) ≥ 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:
# 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.
# 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ţă.
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)
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)
^({$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).
^({$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).
