Soluţii ONIS 2015, Runda 1

Por Costel şi Azerah

Solutia cea mai la indemana la problema aceasta se bazeaza pe metoda programarii dinamice:
Calculam:

dp[i][0] = numarul de submultimi cu suma numerelor para cu primele i numere din sir
dp[i][1] = numarul de submultimi cu suma numerelor impara cu primele i numere din sir

Cazul de baza:

dp[0][0] = 1 (submultimea vida)
dp[0][1] = 0

Relatia de recurenta:

Daca numarul v[i] este par:
- dp[i][0] = 2 * dp[i-1][0]
- dp[i][1] = 2 * dp[i-1][1]
Daca numarul v[i] este impar:
- dp[i][0] = dp[i-1][0] + dp[i-1][1]
- dp[i][1] = dp[i-1][0] + dp[i-1][1]

Complexitate: $O(N)$

Insa, la o inspectie mai amanuntita a dinamicii sau dupa un rationament combinatoric descoperim ca:

Daca exista numai numere pare in sir, raspunsul este 2ⁿ - 1
Altfel este 2^n-1 - 1

Acum, daca ignoram citirea sirului, complexitatea este $O(log N)$

Por Costel şi Algoritmul

Stim ca aloritmul va lua cel putin doua iteratii pentru ca se garanteaza ca exista cel putin o muchie care iese din nodul 1. Pentru ca algoritmul lui Por Costel sa se termine in doua iteratii, trebuie ca doar la prima iteratie sa se produca relaxari ale muchiilor (modificari ale vectorului d). Cand se intra in iteratia a doua trebuie ca in vectorul d sa existe deja valorile drumurilor minime pentru a nu se produce nicio modificare, variabila ok sa ramana cu valoarea 1 si sa nu se mai intre in while a treia oara.

Pentru a rezolva problema sunt necesare niste cunostiinte generale despre problema drumurilor minime intr-un graf, de exemplu, faptul ca reuniunea drumurilor minime din nodul x catre toate celelalte noduri formeaza un arbore (arborele partial al drumurilor minime din x). Observam ca daca muchiile din acest arbore sunt parcurse in ordinea unei parcurgeri din nodul x (DFS sau BFS sau orice fel de parcurgere), drumurile minime se vor propaga complet. Deci solutia va reprezenta o astfel de ordonare a N-1 muchii care formeaza un arbore partial de drumuri minime din nodul 1 iar restul de M-N+1 muchii pot fi interclasate cu acestea in orice fel.

Pentru a construi un arbore partial de drumuri minime din nodul 1, trebuie sa aplicam un algoritm de drum minim. O solutie este chiar Bellman-Ford dar acesta are complexitate $O(N*M)$ chiar si daca il codezi mai bine ca Por Costel. Pentru ca muchiile din graf au cost pozitiv, drumurile minime se pot calcula folosind algoritmul lui Dijkstra

Complexitatea: $O(M*logN)$

Testul pe care pica Bellman-Ford:

Muchiile 1 -> 2, 2 -> 3, 3 -> 4... N-1 - > N, toate de cost 1
Muchiile 1 -> 3, 1 -> 5, 1 -> 7....1 ->N-1/N, prima de cost 10, a doua de cost 20, a treia de cost 30 etc.

Este nevoie de un shuffle foarte norocos al muchiilor din nodul 1 pentru ca algoritmul sa mearga bine.

Por Costel şi Bujor

Constatarea cheie aici este ca daca inmultim matricele B si P obtinem matricea I cu semnificatia: I[i][j] = total expected winnings pentru Bujor in casino-ul i, in ziua j.
Observam ca matricele I care satisfac cerinta finala sunt matricele permutare, printe care se numara si matricea identitate I_n. Deci matricea P poate fi inversa matricei B. Matricea B este garantat inversabila deoarece se garanteaza ca exista solutie la problema (Ecuatia matriceala B*P = I cu det(I) nenul are solutie doar daca det(B) este si el nenul)

Inversa matricei se poate calcula in $O(N^3)$ cu o variatie a algoritmului lui Gauss care se cheama eliminare Gauss-Jordan. Prin inmultiri de linii cu constante, si scadere de linii din alte linii, putem aduce matricea B la matricea I_n. Atunci operatiile pe care le-am efectuat sunt echivalente cu inmultirea cu matricea B^-1. Daca retinem aceste operatii si le aplicam pe matricea I_n, vom obtine matricea B^-1. Mai multe explicatii/informatii se gasesc si aici

Por Costel şi Comisia de Cenzură

Problema aceasta poate fi impartita in doua subprobleme:

Aflarea pozitiilor dintr-un text pe care apar cuvintele dintr-un dictionar
Dandu-se un numar de intervale pe axa Ox, si costuri pe fiecare pozitie de pe axa Ox sa se gaseasca o acoperire a intervalelor (fiecare interval sa aibe cel putin un punct care il acopera) de cost minim.

Subproblema 1

Aceasta problema admite mai multe solutii, insa cea de complexitate optima se foloseste de un automat Aho-Corasick. Va rugam sa-l studiati inainte de a citi mai departe. Vom numi nod terminal un nod din Aho-Corasick in care se termina un cuvant din dictionar. Fiecare nod din automat va avea un vector dinamic mathces, o lista cu indici ai prefixelor din text pentru care cuvantul determinat de acest nod (mai precis de drumul de la radacina la acest nod) este sufix. Atunci cand 'trecem textul prin automat' incarcam fiecare indice i din text (care reprezinta prefixul care se termina la pozitia i) in vectorul matches al nodului la care am ajuns la momentul respectiv. Acesta va fi cel mai lung prefix al unui cuvant din dictionar care este sufix al prefixului i al sirului. Pentru a afla toate prefixele din dictionar care sunt sufixe ale acestui prefix i, este suficient sa copiem continutul vectorului matces al nodului curent in vectorii matches ai nodurilor in care ajungem urmarind pointerul de nepotrivire fail. Apoi, putem scoate pozitiile de potrivire ale cuvintelor din vectorii matches ale nodurilor terminale.

Atentie ! Aici se poate cadea intr-o capcana. Problema garanteaza ca numarul de aparitii ale cuvintelor din dictionar in text nu depaseste 10⁴, dar problema nu garanteaza pentru numarul de aparitii ale prefixelor cuvintelor din dictionar.

Daca avem textul T: aaaaaaa
si un cuvant un dictionar C: aaaaaaa
Numarul de aparitii ale lui C in T este 1 dar numarul de aparitii ale unui prefix al lui C in T este $O(L^2^)$ unde L este lungimea lui C. Urmarind procedeul de mai sus putem da peste o explozie in vectorii matches, dimensiunea lor find de ordinul $O(Nr.aparitii.cuvinte*L^2^)$ . Pentru a remedia acest lucru, vom mentine in fiecare nod o valoare booleana care ne spune daca urmarind pointerul fail mai putem ajunge la un nod terminal. Daca aceasta valoare este false, nu mai copiem continutul vectorului matches al nodului curent mai departe.

Pana acum avem complexitate $O(N + Nr.cuvinte*L + Nr.aparitii.cuvinte*L)$ unde L este lungimea maxima a unui cuvant.

Subproblema 2

Problema aceasta se trateaza prin programare dinamica. Este clar ca putem inlatura intervalele care contin alte intervale. Dinamica de mai jos functioneaza si daca nu facem aceasta reducere, dar o sa consideram ca o facem pentru ca simplifica explicatia:

Intervalele sunt acum lipsite de parantezari deci o sortare dupa capatul stanga reprezinta si o sortare dupa capatul dreapta. Indexam intervalele dupa aceasta ordine. Al i-lea interval este cel cu al i-lea capat stanga. Deoarece alegand o pozitie k de pe axa Ox acoperim o secventa continua de astfel de intervale, putem construi dinamica:

dp[i] = costul minim de a acoperi primele i intervale.

Parcurgem pozitiile de pe axa Ox de la stanga la dreapta. Presupunem ca stim configuratia de intervale. Presupunem ca suntem la pozitia i si stim configuratia de intervale care trece prin aceasta pozitie. Aceasta va fi o secventa continua de intervale - [l..r], unde l este cel mai din stanga interval iar r este cel mai din dreapta. intervalele [1..l-1] trebuiau acoperite cu pozitii mai mici decat aceasta, nu mai avem cum sa le acoperim de aici. Asadar, este necesar si suficient sa actualizam dp[k] = min (dp[k], dp[l-1] + v[i]) pentru oricare k cu l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:

int get_answer (vector<pair<int,int> > intervals)
{
    sort (intervals.begin(), intervals.end());
 
    for (int i = 0; i < intervals.size(); ++i)
    {
        bal[intervals[i].first][0].push_back(i+1);  //bal[i][0] - lista de intervale care incep la pozitia i
        bal[intervals[i].second][1].push_back(i+1); //bal[i][1] - lista de intervale care se termina la pozitia i
    }
 
    for (int i = 1; i <= intervals.size(); ++i)
        dp[i] = inf;
 
    dp[0] = 0;
    int not_present = 0;
    int present = 0;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < bal[i][0].size(); ++j)
        {
            present = max (present, bal[i][0][j]);
        }
 
        for (int j = not_present+1; j <= present; ++j)
        {
            dp[j] = min (dp[j], dp[not_present] + v[i]);
        }
 
        for (int j = 0; j < bal[i][1].size(); ++j)
        {
            not_present = max(not_present, bal[i][1][j]);
        }
    }
 
    return dp[intervals.size()];
}

Dar stati, complexitatea nu devine cumva $O(Nr.aparitii^2^)$ ? De fapt, fiecare interval este parcurs si updatat atata timp cat el contine pozitia curenta. Intervalele sunt de lungime maxim 100 si complexitatea acestei parti este de fapt $O(N + Nr.aparitii*L)$ .

Tinem sa-l felicitam pe Popa Andrei •andreiiii, care a reusit sa rezolve aceasta problema in mod specataculos in ultimul minut.

Por Costel şi Cifrul

Solutia la aceasta problema se foloseste de principiul includerii si excluderii. Vom numara si aduna numarul de coduri care deschid seiful datorita apropierii de primul cod din cele M, de a al doilea cod, de al treilea cod.. apoi le vom scadea pe cele care sunt apropiate simultan de primul si al doilea, de primul si de al treilea, de al doilea si de al treilea.. etc.

Presupunand ca am fixat o configuratie de coduri si stim pentru fiecare i nr[i] = numarul de celule care apartin intersectiei intervalelor corespunzatoare rotitei i. Numarul de coduri 'apropiate' de fiecare din codurile din configuratie este data de nr[1]*nr[2]*nr[3]*..nr[N].

Tot ce trebuie sa facem este construim intersectiile pentru fiecare configuratie, pe fiecare rotita, sa calculam rezultatul si sa il adunam sau scadem din solutie.
Lucrul care poate sa nu fie evident la prima vedere este ca desi intersectia a X intervale pe o axa este un interval (sau multimea vida), pe un cerc, ea nu este interval. Ea poate consta si din M intervale disjuncte. De exemplu:
----------- -----------
------- ---------------
---- ------------------

Cel mai sigur mod de a implementa functia de intersectie este de a ne inchipui ca suntem de fapt pe o axa necirculara. Astfel, intervalele (x,y) cu x > y le despartim in [x,k-1] si [0,y]. Acum, intersectia a X intervale disjuncte cu Y intervale disjuncte este reuniunea intersectiilor fiecare perechi de intervale (a,b) cu a din X si b din Y. Adica functia de intersectie o putem scrie asa:

void intersect (vector<pair<int,int> > X[], vector<pair<int,int> > Y[], vector<pair<int,int> > intersection[])
{
    for (int i = 1; i <= n; ++i)  // pentru fiecare rotita
    {
        for (int j = 0; j < X[i].size(); ++j)
        {
            for (int h = 0; h < Y[i].size(); ++h)
            {
                int front = max (X[i][j].first, Y[i][h].first);
                int end = min (X[i][j].second, Y[i][h].second);
 
                if (front <= end)
                    intersection[i].push_back(make_pair(front, end));
            }
        }
    }
}

Noi vom intersecta mereu o multime de intervale cu un interval de forma (x-D,x+D) care se va transpune in 1 sau 2 intervale necirculare, adica Y[i].size() va fi mereu 1 sau 2. Complexitatea functiei de mai sus este astfel $O(N*M)$ .

Acum, modul in care vom parcurge intersectiile va dicta complexitatea finala. Daca pur si simplu iteram prin cele 2^M configuratii iar pentru fiecare configuratie construim intersectia intervalelor din configuratie de la zero, complexitatea va fi $O(N*M^2 *2^M^)$ .

Complexitatea care rezolva problema este $O(N*M*2^M^)$ care poate fi obtinuta prin metoda backtracking, construind treptat intersectia celor M coduri.

Por Costel şi Invazia Extraterestră

Solutia corecta la aceasta problema presupune cunoasterea structurii de date Arbore de intervale.

Problema se poate rezolva mentinand in fiecare nod al unui arbore de intervale o structura de date auxiliara care sa poata sa raspunda rapid la inserari, stergeri si query-uri de minim (de exemplu, heap). Insa, cum operatiile de inserare si stergere la problema aceasta sunt parantezate corect, este indeajuns o stiva.

Cand primim o inserare, descompunem intervalul primit in cele logN noduri corespunzatoare din arborele de intervale, iar in varful stivei din fiecare din aceste noduri incarcam min(inaltimea noii nave, varful precedent al stivei). La stergere, luam intervalul asociat ultimei inserari (care il vom memora probabil tot cu ajutorul unei stive) si, din nou, il descompunem in cele logN noduri asociate, pe stivele carora apelam pop()(stergem varful).

De notat este ca problema nu necesita lazy-update, intrucat query-urile sunt punctiforme (nu sunt pe interval). Un query va parcurge pe arborele de intervale un drum de la radacina la o frunza. Daca in fiecare dintre nodurile de pe drum, ne uitam la ce se afla in varful stivei, raspunsul pentru query va fi minimul dintre aceste valori.

Complexitatea este $O(M*logN)$

Por Costel şi Livada

Sa consideram o rezolvare prin programare dinamica si o dinamica cu urmatoarea semnificatie:

dp[i][j] = valoarea maxima a unei livezi care contine celula (i,j) si poate contine celule de pe linii ≤ i.

Raspunsul va fi max dintre toate dp[i][j].

O rezolvare in $O(N*M^3^)$ este destul de la indemana. Parcurgem liniile de la 1 la N. Presupuem dinamica calculata pentru liniile < i. Atunci, la linia i, fixam fiecare subsecventa de coloane (j,k) j ≤ k si actualizam in felul urmator:

Definim s(i,j,k) = dp[i][j] + dp[i][j+1] + ... + dp[i][k]
Definim mv(i,j,k) = max(dp[i][j], dp[i][j+1],..., dp[i][k])
Atunci actualizam dp[i][h] = max(dp[i][h], s(i,j,k) + mv(i-1,j,k)) oricare h cu j ≤ h ≤ k

Calcularea lui s, mv precum si actualizarea se pot face parcurgand de la j la k, complexitatea finala fiind cea mentionata mai sus.

Vrem sa coboram complexitatea la $O(N*M^2^)$ . Valorile lui s si mv sunt usor de obtinut in $O(M^2^)$ pe linie parcurgand subsecventele de coloane in modul corespunzator. Problema este cum actualizam ? Vom utiliza o dinamica auxiliara independenta de linii (adica una care se refera doar la o singura linie la un moment dat).

pe linia i, auxdp[j][k] = valoarea maxima a lui dp[i][h] cu h intre j si k.

Definitia ne ajuta mai putin sa intelegem functionalitatea acestei dinamici. Ce facem cu ea este ca atunci cand am calculat s(i,j,k) + mv(i-1,j,k) pentru o subsecventa (j,k) in loc sa facem un for de la j la k, incarcam valoarea in auxdp[j][k]. Dupa ce am parcurs toate subsecventele de coloane, le parcurgem a doua oara, de data aceasta in ordinea inversa a lungimii si actualizam in felul urmator:
* auxdp[j+1][k] = max (auxdp[j+1][k], auxdp[j][k]) cu j < k
* auxdp[j][k-1] = max (auxdp[j][k-1], auxdp[j][k]) cu j < k

La final, valoarea lui dp[i][j] se va afla nicaieri altundeva decat in auxdp[j][j]. Ce am facut practic a fost sa acumulam actualizarile in aceasta dinamica auxiliara iar apoi sa le "impingem spre interior" catre punctele singulare, acelea fiind singurele valori de care avem nevoie mai departe.

Exista si alte moduri de a face reducerea la $O(N*M^2^)$ . Unii dintre voi le-ati aplicat in timpul concursului. Va invitam sa va ganditi la ele.

Por Costel şi Meciul

Aceasta problema se rezuma la urmatorul lucru: Avem un graf bipartit si, primind query-uri de adaugare de muchii, vrem sa stim daca isi pastreaza natura de graf bipartit si, daca da, sa adaugam muchia.

Solutia 1

La fiecare moment, mentinem liste cu noduri, o lista reprezentand o componenta conexa din graf la acel moment (initial avem N liste a cate un singur element fiecare). In plus, pentru oricare nod retinem carei liste ii apartine si, in cadrul acelei componente conexe, in ce 'echipa' se afla. Daca primim un query intre doua noduri care apartin aceleiasi componente conexe, acesta este usor de tratat(NO daca sunt de aceeasi parte, YES daca sunt de parti diferite). Interesant este ce facem daca nodurile sunt din doua componente conexe diferite. Trebuie sa le punem intr-o singura lista cu informatii actualizate. Observam totusi ca nu este nevoie sa ne atingem decat de nodurile uneia din liste. Nodurile dintr-o lista le vom introduce in cealalta lista (lista lor originala o vom elimina) si le vom plasa in 'echipe' relativ la nodurile din aceasta lista. Daca alegem intotdeauna sa mutam nodurile din lista mai mica in lista mai mare, complexitatea va fi $O(M + N*logN)$ . Va lasam pe voi sa va ganditi de ce. (indiciu: nodurile vor apartine in final unei singure liste iar din momentul acela nu vor mai exista mutari, ganditi-va de cate ori poate fi mutat un nod pana sa faca parte din lista finala).

Solutia 2

Distingem 3 cazuri:

Apare o muchie intre doua noduri izolate X si Y. Punem muchia. Utilizam o pereche de culori care nu a mai fost folosita pana acum (a,b). Il coloram X cu a si pe Y cu b.
Apare o muchie intre un nod izolat si un nod neizolat. Punem muchia. Nodul neizolat este deja colorat cu o culoare. Coloram nodul izolat cu perechea acestei culori.
Apare o muchie intre doua noduri neizolate. Daca culorile lor coincid, afisam NO, altfel punem muchia. Sa zicem ca nodurile sunt X si Y iar culoarea lui X este a din perechea de culori (a,b) iar culoarea lui Y este c din perechea de culori (c,d). Vrem sa exprimam ca, de acum in colo, a este echivalent cu d iar b este echivalent cu c. Pentru aceasta putem folosi paduri de multimi disjuncte.

Complexitatea este $O(N + M*log ^* N)$ adica aproximativ $O(N + M)$ .

Por Costel şi Perechile

Daca un baiat are stangacia x, atunci numarul de fete cu care poate dansa este [n/x].
Deci trebuie sa calculam [n/1] + [n/2] + [n/3] + ... + [n/n].
Ne permitem sa calculam suma pana la ${\sqrt{N}}$ . De acolo putem constata ca exista ${\sqrt{N}}$ intervale de numere, pe un interval toate numerele i avand acelasi rezultat al expresiei [n/i]. Putem sa aflam primul si ultimul numar din intervalul care il are ca rezulatat al expresiei pe rez: acestea sunt n/(rez+1) + 1 si n/rez.

O solutie mult mai simpla si mai rapida este sa ne dam seama ca intr-o pereche (a,b) cu a*b ≤ N cel putin unul dintre a si b este ≤ ${\sqrt{N}}$ Putem sa calculam cu formula de mai sus sol = nr. de perechi in care stangacia fetelor este ≤ ${\sqrt{N}}$ . Atunci tot acesta va fi numarul de perechi in care stangacia baietilor este ≤ ${\sqrt{N}}$ . Atunci raspunsul final = 2*sol - cate perechi exista in care atat stangacia fetelor cat si a baietilor este ≤ ${\sqrt{N}}$ . Acesta din urma este chiar [ ${\sqrt{N}}$ ]²

Complexitatea este $O({\sqrt{N}})$

Por Costel şi Pinball

Dandu-se un sir de numere, care este lungimea celui mai lung subsir alternant ? este intrebarea pusa de aceasta problema.

Dificultatea acestei probleme consta in a face urmatoarea constatare:

Valoarea celui mai lung subsir alternant este data de numarul de 'varfuri' din sir:

Un varf este un element v[i] pentru care se intampla una din urmatoarele

v[i-1] < v[i] > v[i+1]
v[i-1] > v[i] < v[i+1]
v[i] este primul element, i = 1
v[i] este ultimul element, i = N

Aceste modificari pot fi suportate in $O(1)$ pe query. Pur si simplu verificam daca elementul curent sau vecinii lui au devenit sau au decazut din statutul de varf.

Complexitate $O(N + M)$

Demonstratie: Vom considera sirul divizat in 'secvente de monotonie'. Doua secvente de monotonie consecutive sunt legate printr-un varf (care apartine amandurora). Fie V = numarul de varfuri si S = numarul de secvente de monotonie. Are loc relatia V = S+1.

Consideram toate solutiile pentru care avem cel mult un element pe fiecare secventa de monotonie: atunci evident sol ≤ S < V.
Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu doua elemente. Daca alegem o secventa de monotonie pe care alegem doua elemente, pe restul secventelor este imposibil sa alegem doua si vom alege cel mult 1, atunci sol ≤ S+1 = V
Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu trei elemente: Nu exista.

Atunci sol ≤ V oricare ar fi sol - lungimea unui sir alternant. Atunci V este valoarea maxima a lungimii unui subsir alternant.

Por Costel şi Pocnitoarea

O problema aparent simpla.. Dar stati.. Nu putem sa precalculam raspunsurile pentru ca nu avem destula memorie. Nu putem sa raspundem offline la query-uri pentru ca avem nevoie de raspunsul de la ultimul query pentru a-l genera pe urmatorul. Ce este de facut ?

Avem foarte mult timp la dispozitie. Nu ne permitem ca pentru un query q sa pornim de la t=0 si sa urmam recurenta pana la t=q. Ce ne permitem in schimb este sa calculam la inceput valorile pana la pasul 10⁷ + 3 si sa retinem doar in anumite locuri rezultatul. Putem sa pornim cautarea atunci de la cel mai apropiat punct inainte de q. Vom precalcula rezultatul la puncte echidistante. Daca retinem rezultatul din ${\sqrt{M}}$ in ${\sqrt{M}}$ producem un echilibru intre timp si memorie. Complexitatea finala va fi $O(M + Q*{\sqrt{M}})$ ca timp si $O({\sqrt{M}})$ ca memorie. Limita de memorie ne permite si mai mult. Cu cat gap-ul dintre punctele precalculate este mai mic, cu atat solutia va fi mai rapida.

Por Costel şi Semipalindroamele

Sa distilam ce inseamna un semiplaindrom. Ca un cuvant sa fie semipalindrom este necesar si suficient ca ultima litera sa fie egala cu prima. Atunci numarul de semipalindroame de lungime N formate din 'a' si 'b' este 2^N-1 - deci K se va incadra in tipul long long. Configuratia binara a lui K va dicta primele N-1 litere din sir (1 inseamna 'b' si 0 inseamna 'a') iar ultima litera este unic determinata de prima. Vedeti ? Nu-i asa greu la Petrozaporksk.