Poti incerca sa vezi ce se intampla daca faci sau nu asta. Nu ai nevoie de "using namespace std" pentru citirea standard dar poate ai nevoie pentru altceva. Data viitoare te rog posteaza in alt loc(de preferat in -> Informatica)

Defapt poate avea maxim T - 2 noduri interne(daca prin nod intern se intelege nod cu grad mai mare ca 2).

Demonstratia e intuitiva:
Arborele are x frunze, y noduri de grad 2 si z noduri interne . Suma gradelor este 2 *(x + y + z) - 2 intr-un arbore cu x + y + z noduri

x + 2 * y + z * k = 2 * x + 2 * y + 2 * z - 2 unde k e media gradelor nodurilor interne(k >= 3)

(k - 2) * z = x - 2

z = (x - 2) / (k - 2) <= (x - 2) / (3 - 1) = x - 2. => La noi in problema fixam doar 5 noduri nu 6

Cu aho corassick poti face pattern match 2d in N^2. Nu cred ca poti face altfel atat de repede. E oarecum util dar singura noastra problema de pattern match 2d se poate rezolva in N^3.

Cred ca totusi cea mai simpla varianta e sa rotim arborele la dreapta(sau stanga nu-mi amintesc exact) pana cand arborele devine lant. Daca faci asta cat nu mai poti in nodul curent si apoi te duci in nodul din dreapta si repeti procedeul complexitatea e O(N) si memoria e O(1).

Cod:

Cod:

for (Node* i = root; i != 0; i = i -> right) {
    while (i -> left != 0) {
        Node* temp = i -> left;
        i -> left = i -> left -> right;
        temp -> right = i;
        i = temp;
    }
    // aici putem face ce vrem cu nodul curent.
} 

Cred ca e O(N) complexitatea pentru ca un nod nu trece in locul tatalui sau decat o data.
Dezavantajul: nu mai avem structura initiala .

Aici memoria se tot declara pe stiva pana la adancimea arborului. Gen daca ai un arbore lant ai go(radacina) in care ai go(radacina -> left) in care ai go(radacina -> left -> left) s.a.m.d in total memoria fiind inaltimea arborului(care nu e O(1)).

Solutie:
Ma gandesc ca daca se poate modifica arborele(adica informatiile left, right nu sunt constante) ar merge sa modificam arborele astfel incat sa avem un query liniar(adica un query apeleaza doar unul singur nu mai multe ca sa se poata rezolva totul iterativ) de forma(unde sunt, de unde vin) si la orice moment arborele curent traversat in inordine sa ne dea ce ne dorim(chair daca forma lui nu e cea initiala).

Sa ne gandim ca mereu suntem in radacina. Si avem query(current_node, father_node). Trebuie dupa ce traversam acest nod sa trecem prin nodul tata. Deci putem modifica astfel nodul curent:
1) Tinem minte fiul stang
2) Fiul drept devine fiul stang
3) father_node(nodul in care trebuie sa ne intoarcem) devine fiul drept.

Iar apoi facem query din nou pentru fiul stang si nodul curent.

Cod:

Node *current_node, *father_node, *NIL;
current_node = root;
father_node = NIL = new Node(); // sa stim cand sa ne oprim facem un nod special
while(current_node != NIL) {
    Node *temporary_node = current_node -> left;
    current_node -> left = current_node -> right;
    current_node -> right = father_node;

    father_node = current_node;
    if (current_node -> left != 0) {
        current_node = current_node -> left;
    }
    else {
        current_node = current_node -> right;
    }
}

Sper ca e corect ce zic.

L.E: E gresit. E foarte gresita.

Si eu am incercat si am ajuns la aceeasi concluzie. std::sort chiar se comporta la fel de bine, chiar mai bine uneori.

Asa merge interactiv. Alta utilitate nu vad, DF-ul tot e varianta mai simpla.

Solutia O(N) cu hashuri e exact cea din primul post. Mai exact pentru fiecare element tinem capatul din stanga si capatul din dreapta al intervalului din care apartine. Atunci cand dam de un element cu valoarea x facem urmatorii pasi

1) Daca l-am intalnit il ignoram, sarim pasii urmatori
2) Daca exista in hash x - 1 unim hashul lui cu elementul curent
     mai exact fie [y, x - 1] intervalul din care apartine x - 1(nu se poate mai la dreapta pentru ca pana la momentul actual nu exista x)
     updatam in hash-ul lui y ca intervalul e [y, x] si la fel si in hash-ul lui x.
3) Daca exista in hash x + 1 unim intervalul lui x cu cel al lui x + 1 pe aceeasi idee ca la pasul 2

In total la un pas facem un numar constant de operatii si sunt numar constanti de pasi => pentru fiecare element facem un numar constant de operatii => complexitate O(N).

Aduce a paduri de multimi disjuncte dar este o particularitate.

Pentru Cosmin Negruseri: Exista vreo solutie care nu foloseste hash-uri si e mai buna de O(N log N)?

asta e N log* N. Cred ca se asteapta o solutie mai buna.

Later Edit:
Se poate totusi implementa in O(N) solutia cu multimi disjuncte datorita particularitatii problemei(mai exact faptul ca niciodata nu vei uni doua multimi decat dupa elemente de la capetele lor, deci informatii legate de multimea unui element nu trebuie updatate decat in capete)

Pentru Patcas Csaba. Nu se garanteaza nicaieri asta.
Pentru Andrici Cezar. Se cere suma ariilor tuturor zonelor peste care se suprapun exact K dreptunghiuri.

Pentru intrebarea ta am putea considera cazul urmator
3
1 1 3 3
2 2 4 4
1 2 3 3

Raspunsul in aceasta situatie este 1. Intersectia primelor doua(2 2 3 3) face parte si din intersectia dintre al doilea si al treilea. Doar zona 1 2 2 3 care face parte din intersectia dintre primul si al treilea este o zona ce apartine de exact 2 dreptunghiuri.

Pentru Rares Buhai.
Da, scuze de confuzie.
Pentru Tudorica Andrei acest raspuns demonstreaza ca nu exista mereu un prieten care spune adevarul.

Nu.

Rezolvat.

Raspunsul este 2.  

să precizeze un număr posibil corect de mincinoşi

In cazul tau, ceilalti doi nu mint, deci numarul de mincinosi nu este corect.

Nu obligatoriu. Dar poate fi.

Nu.

DA

Catre Paul:
Nimeni nu garanteaza ca un om care in general se pricepe mai bine ca altul va face mereu mai bine ca acesta. Sunt zeci de exempledin care putem enumera: barajele de la lot, natioanala si daca inca nu l-am inclus pe Bogdan Tataroiu in ecuatie avem si campionul.
Si totusi un concurs de 36 de ore nu cred ca arata atat de mult performanta unui om. La lot ai 3 probleme in 5 ore deci ar iesi 10 probleme in 17 ore. Daca ai avea mai mult timp probabil clasamentele s-ar schimba din cauza vitezii de gandire ar unor oameni, din cauza vitezii de implementare, etc. Nu s-ar schimba radical, dar s-ar schimba. Aici vorbim de performanta in concursuri dupa cum se vede nu de cea in cercetare
Asta se aseamna foarte mult si cu clasamentul din arhiva vs performanta din concursuri. Poti face multe probleme in arhiva pentru ca practic ai un timp nelimitat insa in regim de concurs ->  .
Si legat de rating: o crestere de la nimic la rosu pe infoarena nu valoreaza nici cat o crestere din gri in verde pe topcoder asa ca nu vad rostul comparatiei.

Am testat sursa lui Gavrila Vlad. Se pare ca el inca ia 100. Deocamdata pare buna limita incercati sa mai optimizati.

Sunt surse care iau 100(cu timpi sub 0.5). Nu cred ca aceasta problema ar trebui sa aiba limita largita doar pentru ca nu intra solutia oficiala.
Apropo vezi ca tu iei si un Killed By Signal 11

Am modificat limita. Daca mai sunt probleme te rog semnaleaza.

Iei la fel, cred ca ar trebui sa fie ok.

Mai "mica" vrei sa zici nu?
Sursa mea intra in 0.06, a ta intra in 0.12 asa ca am pus limita 0.15. Cred ca ar trebui sa fie de ajuns

Eu sincer pot sa zic ca pe mine m-a ajutat ICHB-ul nu neaparat prin ce am invatat la el dar prin concurenta. Fiind in orasul meu natal nu puteam observa concurenta atat de mult cat am putut la ICHB. Ca individual iti este destul de greu sa te autoconvingi sa devii mai bun, dar fiind inconjurat de un colectiv foarte bun in ceea ce faci esti impins sa devii mai bun.