h1. 'Problema cu becuri':problema/pcb

Construim un graf cu $N + 1$ noduri in care fiecare nod reprezinta o stare. Starea initiala este reprezentata de nodul $0$. Fiecare nod $i > 0$ va reprezenta starea in care sunt aprinse doar becurile $[0,i-1]$.

Construim un graf cu $N + 1$ noduri in care fiecare nod reprezinta o stare. Starea initiala este reprezentata de nodul $1$. Fiecare nod $i > 1$ va reprezenta starea in care sunt aprinse doar becurile $[1,i-1]$.

Pentru fiecare comutator care schimba becurile din intervalul $[a,b]$ adaugam o muchie intre nodurile
$a$ si $b+1$. Explicatia este: $a$ reprezinta becurile aprinse in intervalul $[0,a-1]$ la care se adauga
cele din intervalul $[a,b]$ si rezulta $[0,b]$, adica nodul $b+1$.

Pentru fiecare comutator care schimba becurile din intervalul $[a,b]$ adaugam o muchie intre nodurile $a$ si $b+1$. Explicatia este: $a$ reprezinta becurile aprinse in intervalul $[1,a-1]$ la care se adauga cele din intervalul $[a,b]$ si rezulta $[1,b]$, adica nodul $b+1$.

Deci, putem aprinde becurile $[0,X-1]$ daca exista un drum de la nodul $0$ la nodul $X$. Raspunsul la problema va fi distanta minima a unui astfel de drum, ceea ce putem afla cu o 'parcurgere in latime':problema/bfs (deoarece toate muchiile au costul $1$).

Deci, putem aprinde becurile $[1,X-1]$ daca exista un drum de la nodul $1$ la nodul $X$. Raspunsul la problema va fi distanta minima a unui astfel de drum, ceea ce putem afla cu o 'parcurgere in latime':problema/bfs (deoarece toate muchiile au costul $1$).

Solutia are complexitatea $O(N + M)$.

Acum singura problema care ne mai ramane este unirea a doua noduri a si b intr-un singur nod c (altfel spus, unirea a doua jumatati de interval intr-un singur interval, mentinand toate informatiile de mai sus). Informatiile legate de capetele noului interval sunt usor de calculat dupa urmatoarele formule intuitive:
== code(cpp) |

a.st = b.st;
a.dr = c.dr;

c.st = a.st;
c.dr = b.dr;

==
Calcularea sumei noului interval se obtine prin adunarea sumelor intervalelor a si b.
== code(cpp) |

a.s1 = b.s1 + c.s1;

c.s1 = a.s1 + b.s1;

==
Calcularea noului s2 este putin mai complexa:
== code(cpp) |

a.s2 = b.s2 + (c.s2 + c.s1 * (b.dr - b.st + 1));

c.s2 = a.s2 + (b.s2 + b.s1 * (a.dr - a.st + 1));

==
Problema a fost aleasa drept cea mai grea problema a setului pentru ca rezolvarea presupunea cunoasterea si aplicarea teoriei, dar si o atentie sporita intr-o implementare laborioasa.