==include(page="jc2023/solutii/omidamincinoasa")==

==include(page="jc2023/solutii/jupanul")==
 
 
h2. 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.
 
h2. 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^({$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 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
 
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 $%$ 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 marke

==include(page="jc2023/solutii/jupanul")==