Solutia problemei Aliniate

Multumim lui Puscasu Felix •felixi pentru editorial!

Solutie O(1) - subtask 5 puncte

Avem conditia ca intervalele nu se intersecteaza ne garanteaza ca vom putea mereu satisface cerintele respectivelor intervale.
O metoda de a construi solutia este de a pune pe o pozitie dintr-un interval valoarea ceruta de acesta si pe restul pozitiilor ramase valoarea 1.

Solutie O(N*log(N)) - subtask 30 puncte

Datorita conditiei de "aliniere" si a faptului ca toate numerele din input sunt impare, deducem ca intervalele pot avea doar lungimea 1.
Daca ar avea o lungime mai mare de 1 si ar fi si o putere de 2, am avea cel putin un capat cu o valoare para, deci contradictie.

Tot ce ne mai ramane sa verificam acum este daca se contrazic doua restrictii din datele de la intrare direct una cu alta.
Putem salva intervalele unitate intr-o structura de date de tip map din stl pentru verificare.

Solutie O(N*log(N)) - 100 puncte

Vom avea nevoie de cateva observatii:

1. Putem verifica o structura de tip map din stl daca doua intervale din input se contrazic direct.
2. Intervalele aliniate formeaza de fapt un arbore binar perfect si/sau complet (Toate nodurile mai putin frunzele au exact 2 fii). Vom asocia astfel fiecarui nod din arbore un interval din input, astfel incat radacina reprezinta intervalul
3. Daca ignoram puterile de 2 intr-un numar, putem cu un singur numar sa trecem de la orice x la alt y datorita teoremei euler.

Cum nu putem tine in memorie intreg arborele va trebui sa construim doar nodurile care ne intereseaza. Observam ca ne intereseaza doar nodurile date de setul format din intervalele date si toti stramosii lor. O sa avem astfel maxim N*log(N) noduri.
Putem calcula o dinamica in fiecare nod care sa ne spuna daca putem sau nu construi acest nod.
Pentru fiecare nod o sa avem nevoie de urmatoarele:

1. Pentru fiecare nod, vom avea nevoie sa stim daca avem cel putin un element "nefixat", adica daca putem folosi un element din acest interval pentru a satisface o restrictie in unul din stramosi, daca este cazul.
2. Puterea de 2 "ceruta" de acest interval. Deoarece lucram modulo o data ce apare un 2 ca factor, nu mai putem scapa de el, mai rau, o data ce avem un 0, orice stramos va avea valoarea 0
3. Ignorand puterile de 2, ne intereseaza ce restrictie avem pentru acest nod. (Produsul format din elementele ei)

Impreuna cu a 2-a observatie de mai sus, putem memora un singur numar pentru restrictia valorii produsului unui interval.

Intr-o maniera DFS, vom calcula aceasta dinamica, avand diferite cazuri.
Frunzele sunt initializate cu valorile din input si vor fi marcate ca "pline", adica nu mai putem modifica niciun element din ele.
Pentru un nod, avem 2 cazuri principale:

1. nu avem restrictie data in input pentru interval. Avem de calculat doar produsul restrictiilor celor 2 fii. Pentru fii inexistenti putem presupune ca avem numai valori de 1, dar atentie, putem modifica aceste valori pentru restrictii cerute de eventualii stramosi.
2. avem o restrictie pentru nod. In primul rand trebuie sa verificam daca fii cer in total o putere de 2 mai mare decat restrictia noastra din nod (Daca da, nu avem solutie). Daca avem cel putin un fiu lipsa, putem folosi un element din celalalt fiu pentru a ne rezolva restrictia din nodul dat, nod. Daca in schimb ambii fii au restricti si sunt si marcati ca plini, atunci verificam ca produsul restrictiilor fiilor sa corespunda cu restrictia din nod.

Pentru a implementa elegant structura de arbore, vom construi dupa citirea intervalelor un nod radacina, si apoi, pentru fiecare interval vom construi "un path" pana la nodul asociat intervalului. Este asemanator ca adaugarea unui sir de caractere intr-o trie.
Detalii de implementare si alte trucuri se gasesc la sursa Submisie