h1(#transform3). 'Solutia':summer-challenge-2021/solutii/transform3 problemei 'Transform3':problema/transform3
h2. Soluţia cu $2N + 2QlogN$ muchii
Peste şirul iniţial de lungime $N$ generăm un arbore de intervale. Nodurile interne vor avea valori începând de la $N+Q+1$ (pentru că nodurile de la $N+1$ la $N+Q$ sunt rezervate pentru rezolvarea restricţiilor problemei). Pentru $N = 10$ şi $Q = 5$, un exemplu de arbore de intervale este:
!{width: 300px; display: block; margin-left: auto; margin-right: auto}summer-challenge-2021/solutii/transform3?transform3-img1.png!
Până acum am folosit $2N$ muchii (deoarece un arbore de intervale construit peste un şir de lungime $N$ are lungimea maxim $2N$).
Pentru rezolvarea unei restricţii, putem să ne folosim de acest arbore de intervale astfel: ştim că orice interval $1 ≤ L ≤ R ≤ N$ poate fi acoperit cu maxim $2logN$ alte sub-intervale corespunzătoare unor noduri ale arborelui. Astfel, pentru fiecare restricţie, putem să tragem maxim $2logN$ muchii de la nodul corespunzător restricţiei ({$N+1 ≤ nod ≤ N+Q$}) la toate nodurile din arborele de intervale de care avem nevoie. De exemplu, dacă $[L{~1~}, R{~1~}] = [2, 6]$ si $[L{~2~}, R{~2~}] = [3, 9]$, vom trage următoarele muchii (restul restricţiilor au fost omise pentru claritate). În total vom folosi deci $2N + 2QlogN$ muchii.
!{width: 300px; display: block; margin-left: auto; margin-right: auto}summer-challenge-2021/solutii/transform3?transform3-img2.png!
h2. Soluţia cu $4N + 2Q$ muchii
Pentru a reduce numărul de muchii, trebuie să facem următoarele observaţii:
* Ideile bazate pe arbori duc în general la complexităţi "logaritmice" (apare un log prin complexitatea finală)
* Numărul de muchii cerut este $4N + 2Q$ care nu conţine niciun logaritm (deci este un hint că soluţiile bazate pe arbori nu duc la soluţia dorită)
* Nicăieri în soluţia precedentă nu ne folosim de proprietatea intervalelor din enunţ.
Aşadar, în loc să plecăm de la un arbore, vom încerca să plecăm de la o structură "liniară", care în cazul nostru este o "coadă simulată cu $2$ stive". Mai concret:
Fiecare interval din cele $Q$ îl vom sparge în alte $2$ sub-intervale (un prefix şi un sufix). Aceste $2$ sub-intervale le vom retine folosind $2$ stive puse una lângă alta. De exemplu o spargere pentru intervalul $[4, 11]$ poate fi:
* $leftStack$: $6, 5, 4$
* $rightStack$: $7, 8, 9, 10, 11$.
Pentru fiecare din cele Q intervale date, vom încerca să le spargem în $2$, folosindu-ne de informaţia de la intervalul precedent (acolo unde este posibil). Algoritmul simulat pentru intervalele $[5, 10], [7, 12], [9, 13], [12, 14], [12, 15], [14, 17]$ este:
table(stack-uri). |_. ID |_. Interval |_. $leftStack$ |_. $rightStack$ |
| $1$ | $[5, 10]$ | $10, 9, 8, 7, 6, 5$ | - |
| $2$ | $[7, 12]$ | $10, 9, 8, 7$ | $11, 12$ |
| $3$ | $[9, 13]$ | $10, 9$ | $11, 12, 13$ |
| $4$ | $[12, 14]$ | $14, 13, 12$ | - |
| $5$ | $[12, 15]$ | $14, 13, 12$ | $15$ |
Modul de construcţie prezentat anterior este foarte asemănător cu modul în care este stocat $std::deque$ în memorie şi este un şmen util în informatica de olimpiadă.
Mai departe, observăm că fiecărei stive la un moment dat îi corespunde un interval compact (de exemplu, stivei cu elementele ${10, 9, 8, 7}$ îi corespunde intervalul $[7, 10]$) şi mai mult, unele intervale sunt incluse in altele (intervalul stivei ${10, 9, 8, 7}$ este inclus în intervalul stivei ${10, 9, 8, 7, 6, 5}$ sau intervalul stivei ${11, 12}$ este inclus în intervalul stivei ${11, 12, 13}$).
Putem aşadar să atribuim fiecărei stive la un anumit moment de timp câte un interval (identificat printr-un cod unic mai mare strict decât $N+Q$) iar de la un interval oarecare putem să tragem muchie către cel mai mare interval inclus în interiorul sau (dacă există) şi câte o muchie la toate elementele neacoperite de acesta. În final, pentru fiecare restricţie, vom trage muchii de la nodul său corespunzător din intervalul $[N+1, N+Q]$ la cele maxim $2$ stive in care se va sparge intervalul.
Pentru exemplul din enunţ, algoritmul ar arăta cam aşa:
|_. ID |_. Interval |_. $leftStack$ |_. $rightStack$ |_. cod $leftStack$ |_. cod $rightStack$ |
| $1$ | $[1, 3]$ | $[1, 3]$ | - | $8$ | - |
| $2$ | $[2, 3]$ | $[2, 3]$ | - | $9$ | - |
| $3$ | $[3, 4]$ | $[3, 3]$ | $[4, 4]$ | $10$ | $11$ |
!{width: 300px; display: block; margin-left: auto; margin-right: auto}summer-challenge-2021/solutii/transform3?transform3-img3.png!
O ultimă observaţie este necesară pentru a obţine $100$ de puncte: observăm ca $leftStack[i]$ poate fi creat doar din $leftStack[i + 1]$ (asta dacă la pasul $i+1$ intervalul nu este creat din nou), respectiv $rightStack[i]$ poate fi creat din $rightStack[i - 1]$ (dacă exista). Dacă atribuim la fiecare pas un cod unic fiecărei din cele $2$ stive la un moment de timp, am obţine $2Q$ coduri distincte. În schimb, dacă atribuim coduri unice fiecărui interval distinct (cu alte cuvinte, nu atribuim coduri distincte dacă $leftStack[i] = leftStack[i + 1]$ sau $rightStack[i] = rightStack[i - 1]$), atunci numărul de coduri atribuite se reduce la maxim $2N$, maxim $N$ pentru fiecare din cele $2$ stive. Demonstraţia este următoarea (demonstrăm pentru $leftStack$, pentru $rightStack$ se poate demonstra similar): $leftStack[i]$ este fie construit din $leftStack[i - 1]$ eliminând un prefix (schimbăm codul doar dacă acest prefix este nenul), fie reconstruită de la $0$. Cum la fiecare pas, capătul stâng al intervalului asociat acestei stive creşte cu cel putin o poziţie, acesta fiind maxim $N$, numărul de coduri distincte asociate pentru toate stivele $leftStack$ la toate momentele de timp este maxim $N$.
Scrie aici despre summer-challenge-2021/solutii/transform3
