h1. 'Solutia':jc2023/solutii/permdist problemei 'Permdist':problema/permdist

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

h2. Subtaskurile 1-3, $20$ puncte

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$})^: 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$})^: 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).