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

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