h1. Solutii Copii3
Toate solutiile prezentate mai jos rezolva queryurile online.
Ambele solutii prezentate mai jos rezolva queryurile online.
h2. Solutia de complexitate <tex>O(Q * N)</tex> timp si <tex>O(N)</tex> memorie
h2. Solutia 1
Un _greedy_ care ar rezolva corect fiecare query in parte ar fi urmatorul: Cat timp mai exista copii in interval, se alege cel a carui stramutare ar fi cat mai putin costisitoare si se muta. Astfel, fie cel mai din stanga copil din interval se va muta pe cel mai apropiat scaun liber din stanga din afara intervalului, fie cel mai din dreapta copil se va muta pe cel mai apropiat scaun liber din dreapta din afara intervalului. Pentru a calcula costul obtinut de acest algoritm, este suficient sa se mentina doua perechi de pointeri (pozitiile celui mai din stanga, respectiv din dreapta copil din interval si pozitiile celui mai apropiat scaun liber din afara intervalului in stanga, respectiv in dreapta), realizand maxim $N$ pasi la fiecare query.
h2. Catre solutii mai rapide
h3. Observatie
Pentru un interval de query $[l, r]$ fixat, va exista o pozitie $p$ unde toti copii din intervalul $[l, p]$ se dug "la stanga", si toti copii din intervalul $[p+1, r]$ se duc "la dreapta" (caci daca aceasta nu ar exista, ar fi un copil ce se duce "la stanga" care e mai la dreapta ca un copil ce se duce "la dreapta", care e evident neoptim).
In continuare ne vom folosi de definirea functiei $f(l, r, p)$ ca fiind costul daca toti copii din $[l, p]$ ar merge "la stanga", si toti copii din $[p+1, r]$ ar merge "la dreapta".
h3. <tex>HINT</tex>
h3. Cum il gasim pe $p$ presupunand ca am putea afla rapid orice valoare a functiei $f$?
Rezolvati problema pentru cazul in care, pentru fiecare query, $R - L + 1$ este o putere a lui $2$.
Observatia importanta este ca functia $g(p) = f(l, r, pozitia celui de al p-lea copil din [l, r])$ este "aproape" unimodala ; mai exact, aceasta poate avea $2$ minime, dar acestea trebuie atunci sa fie adiacente. Mai mult, observam oricare valori egale in $p$ trebuie sa fie una in stanga si una in dreapta minimului. Pentru a demonstra acest lucru, este nevoie sa observam ca, cat timp cuplam copii care merg la stanga (respectiv la dreapta) cu pozitiile goale cele mai la dreapta (respectiv la stanga) care sunt la stanga (respectiv la dreapta) lui $[l, r]$, putem cupla oricare copil cu oricare spatiu (din comutativitate); iar astfel, arbitrar, putem alege sa cuplam al $i$-lea copil de la stanga (respectiv la dreapta) lui $[l, r]$ cu al $i$-lea copil de la dreapta la stanga (respectiv de la stanga la dreapta) la stanga (respectiv la dreapta) lui $[l, r]$. Astfel, putem cauta ternar valoarea lui $p$ (avand in vedere cazul special de egalitate).
h3. <tex>O(Q * N)</tex> timp, <tex>O(N)</tex> memorie
h3. Ce inseamna cautare ternara?
Atunci cand avem de a face cu o functie <tex>h : A \to B</tex> "aproape" unimodala (care are propietatea ca mai intai creste (descreste) strict, apoi ramane constanta, apoi descreste (creste) strict), putem gasi cu <tex>O(log|A|)</tex> interogari de genul "cu cat este egal <tex>h(x)</tex>?" valoarea maxima (minima) atinsa de functie. Se disting mai multe cazuri:
* Cazul in care <tex>A = \mathbb{N} \cap [a, b]</tex> este cel care ne intereseaza pe noi. In acest caz putem crea o functie auxiliara <tex>j : (A \setminus \{ max(A) \}) \to \{ -1, 0, 1 \}</tex> cu <tex>j(x) = sign(h(x) - h(x + 1))</tex>. Practic, cat timp functia creste, <tex>j(x) = -1</tex>, cat timp este constanta, <tex>j(x) = 0</tex> iar cat timp scade <tex>j(x) = 1</tex>. Din moment ce <tex>h</tex> este "aproape unimodala", <tex>j</tex> este monotona, iar a gasi varful functiei <tex>h</tex> este echivalent cu a gasi primul "1" sau ultimul "-1" (primul "-1" sau ultimul "1") sau orice "0" pe functia <tex>j</tex>. Aceasta se rezolva cu cautare binara in <tex>O(log|A|)</tex> interogari ale functiei pe <tex>j</tex>, iar in termeni de interogari ale functiei <tex>h</tex>, este dublu, ceea ce nu schimba complexitatea. *De retinut* este felul in care am fentat functia unimoadala cu o functie monotona echivalenta.
* Cazul in care $A = [a, b]$ necesita o explicare a complexitatii <tex>O(log|A|)</tex>. De cele mai multe ori, nu este necesara sau posibila o calculare $100%$ precisa a rezultatului in aceste cazuri, prin urmare se doreste calcularea acestuia cu o precizie data, sa zicem <tex>P = 10^{-6}</tex>. Asadar nici cautarea pozitiei varfului nu se face la infinit, ci pana este satisfacuta precizia. Prin urmare, putem considera <tex>|A| = \frac{b - a}{P}</tex>. Rezolvarea acestuia se poate face ocazional asemanator cu primul caz, definid <tex>j(x) = h(x) - h(x + P)</tex>, dar precizia acestui calcul nu este prea buna, prin urmare se cauta o alta solutie. Denumirea de "ternara" vine de la faptul ca acum vom folosi un algoritm care foloseste doi pivoti. Astfel, in intervalul $[a, b]$ se aleg doua puncte $c < d$, si in functie de valorile functiei in punctele $c$ si $d$, intervalul ramas este fie $[a, d]$, fie $[c, b]$. Astfel, se pot alege punctele $c$ si $d$ astfel incat sa fie impartit intervalul in 3 bucati egale. Aceasta solutie poate fi aplicata si pentru primul caz, si de aceea am explicat-o aici. Cu toate acestea, o 'imbunatatire':https://en.wikipedia.org/wiki/Golden-section_search a acestei solutii este posibila in ceea ce priveste constanta numarului de interogari.
* Cazurile in care <tex>A = \mathbb{Q} \cap [a, b]</tex> sau altele sunt mai putin uzuale si nu le vom discuta aici.
h2. Solutia de complexitate <tex>O(N * logN + Q * logN * logN)</tex> timp si <tex>O(N * logN)</tex> memorie
Nu ne-a mai ramas nimic de facut decat sa calculam cat mai repede $g(x)$, pentru a raspunde interogarilor cat mai repede. In functie de aceasta, vom obtine algoritmi mai mult sau mai putin eficienti. Putem calcula $g(x)$ in <tex>O(logN)</tex> daca precalculam un tablou definit asa:
Un _greedy_ care ar rezolva corect fiecare query in parte ar fi urmatorul: Cat timp mai exista copii in interval, se alege cel a carui stramutare ar fi cat mai putin costisitoare si se muta. Astfel, fie cel mai din stanga copil din interval se va muta pe cel mai apropiat scaun liber din stanga din afara intervalului, fie cel mai din dreapta copil se va muta pe cel mai apropiat scaun liber din dreapta din afara intervalului. Pentru a calcula costul obtinut de acest algoritm, este suficient sa se mentina doua perechi de pointeri (pozitiile celui mai din stanga, respectiv din dreapta copil din interval si pozitiile celui mai apropiat scaun liber din afara intervalului in stanga, respectiv in dreapta), realizand maxim $N$ pasi la fiecare query.
* $d[directie][t][pozitie_start] = pair < costul minim de a trimite 2^{_t_}^ copii plecand de la _pozitie start_ in directia stanga sau dreapta, in functie de _directie_ (care este un $bool$) ; pozitia primului scaun liber in directia data de _directie_ daca se ocupa 2^{_t_}^ scaune plecand de la _pozitie_start_ >$
h3. ...
si unul asemanator, doar ca, in loc sa priveasca scaune libere, priveste copii, adica scaune ocupate, atunci vom putea, prin descompunerea in puteri de $2$ a lui $x$, sa mutam copii atat din stanga cat si din dreapta spre scaunele libere cu cost minim. Cum descompunerea in puteri de $2$ inseamna <tex>O(logN)</tex> pasi, numarul de interogari de acest gen per query este de <tex>O(logN)</tex> iar precalcularea are complexitate <tex>O(N * logN)</tex> timp si memorie, se obtine algoritmul de 60 de puncte.
h2. Solutia 2
h2. Solutia de complexitate <tex>O(N + Q * logN)</tex> timp si <tex>O(N)</tex> memorie
O prima observatie impotanta (defapt aceeasi ca observatia importanta de la problema Wiring de la IOI 2017) este aceea ca, pentru un interval de query $[l, r]$ fixat, va exista o pozitie $p$ unde toti copii din intervalul $[l, p]$ se dug "la stanga", si toti copii din intervalul $[p+1, r]$ se duc "la dreapta" (caci daca aceasta nu ar exista, ar fi un copil ce se duce "la stanga" care e mai la dreapta ca un copil ce se duce "la dreapta", care e evident neoptim).
Oare putem, pentru un interval $[l, r]$, si o pozitie $p$ in acest interval, sa gasim "repede" care ar fi costul daca toti copii din $[l, p]$ ar merge "la stanga", si toti copii din $[p+1, r]$ sa mearga "la dreapta"? Sa numim aceasta valoare $f(l, r, p)$.
Raspunsul este da: $f(l, r, p)$ este egala cu suma pozitiilor copiilor din $[l, p]$ minus suma pozitiilor copiilor din $[p+1, r]$, plus suma indicilor primilor $(nr. copii din [p+1, r])$ spatii goale din dreapta lui $r$, minus suma indicilor ultimilor $(nr. copii din [l, p])$ spatii goale din stanga lui $l$. Toate valorile mentionate pot fi gasite in $O(1)$ cu ajutorul unor precalculari usoare in $O(n)$.
Acum, cum gasim acea pozitie optima a lui $p$ ?
Observatia importanta este ca functia $g(p) = f(l, r, pozitia celui de al p-lea copil din [l, r])$ este "aproape" unimodala ; mai exact, aceasta poate avea $2$ minime, dar acestea trebuie atunci sa fie adiacente. Mai mult, observam oricare valori egale in $p$ trebuie sa fie una in stanga si una in dreapta minimului. Pentru a demonstra acest lucru, este nevoie sa observam ca, cat timp cuplam copii care merg la stanga (respectiv la dreapta) cu pozitiile goale cele mai la dreapta (respectiv la stanga) care sunt la stanga (respectiv la dreapta) lui $[l, r]$, putem cupla oricare copil cu oricare spatiu (din comutativitate); iar astfel, arbitrar, putem alege sa cuplam al $i$-lea copil de la stanga (respectiv la dreapta) lui $[l, r]$ cu al $i$-lea copil de la dreapta la stanga (respectiv de la stanga la dreapta) la stanga (respectiv la dreapta) lui $[l, r]$. Astfel, putem cauta ternar valoarea lui $p$ (avand in vedere cazul special de egalitate). Complexitatea finala este de $O(N + Q * log(N))$.
Iata o modalitate de calcul a lui $g(p)$ mai eficienta: $f(l, r, p)$ este egala cu suma pozitiilor copiilor din $[l, p]$ minus suma pozitiilor copiilor din $[p+1, r]$, plus suma indicilor primilor $(nr. copii din [p+1, r])$ spatii goale din dreapta lui $r$, minus suma indicilor ultimilor $(nr. copii din [l, p])$ spatii goale din stanga lui $l$. Toate valorile mentionate pot fi gasite in <tex>O(1)</tex> cu ajutorul unor precalculari asemanatoare sumelor partiale in <tex>O(n)</tex>.
h2. Solutia 3
Prin urmare, cu aceste precalculari liniare, putem raspunde pe loc la fiecare query, in doar <tex>O(logN)</tex> interogari ce sunt rezolvate in timp constant pe o functie "aproape" unimodala.
/// Anybody, please...
