'Solutia' pentru problema 'Permdist':

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

Subtaskurile 1-3, 20 puncte:

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.

Subtaskul 4, 36 puncte:

h2. Subtaskul 4, $36$ puncte

Notăm cu 'd(T, x, y)' (distanţa în T de la x la y) ca 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'.

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

Să descompunem cele două permutări în cicluri.

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.

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.

h2. Subtaskul 6, $100$ puncte

Reformulare (2): Dacă în fiecare ciclu am desemna un reprezentant (aleator), iar pentru fiecare valoare x din ciclul respectiv am nota distanţa acestuia de la reprezentant cu 'DA[x]' pentru permutarea A, respectiv 'DB[x]' pentru permutarea B, iar cu 'LA[x]' şi 'LB[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 '(DA[y] - DA[x]) mod LA[x] = (DB[y] - DB[x]) mod LB[x]'.

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:

Cum pentru toate numerele 'LA[x] = LB[x] = N', putem asocia fiecărei valori x câte un coeficient 'C[x] = (DA[x] - DB[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 '(DA[x] - DB[x]) mod N = (DA[y] - DB[y]) mod N <=> (DA[y] - DA[x]) mod N = (DB[y] - DB[x]) mod N', iar din din (2) aceasta este corect. Se poate utiliza un vector de frecvenţă pentru calcularea numărului de valori y care au 'C[y] = C', 'C' fiind variabil după x. Complexitate timp (şi memorie): O(N)

# 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ţă.

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 ca x şi pentru care se fixează o ierarhie între valorile din diferenţe (adică y să respecte că 'DA[x] < DA[y]', 'DB[x] < DB[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.

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)

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 subsecvenţă 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ă. Singura problemă vine de la valorile u care au 'I[u] < I[r]', 'I[u] + DB[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ă problemă. Introducem noţiunea şirului 'Cycle^2(B)', a cărui definiţie este similară, doar că scrierea fiecărui ciclu (ca elemente consecutive din parcurgerea 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 variantă lucrăm atâta timp cât se păstrează aceste proprietăţ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 'DB[u]' unităţi mai în faţă în şir (într-atât ca (3) se respectă). Acum, structura dată (a markerelor) ne poate răspunde corect la queryuri. Singura problemă este că aceasta este (în momentul de faţă) descrisă ca să poată să răspundă corect (4) doar la queryuri privind pe r. Trebuie să reparam 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 schimba (dacă 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)' poziţii în urmă.
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ţă 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$})^: 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).