Nu am rezolvat problema. Dar vezi ca poti sa iei kbs si daca spargi stiva. Am inteles ca faci un DFS. Daca e recursiv asta ar putea sa fie. Incearca sa il implementezi iterativ.

Eu tin minte ca il picam deoarece cand scadeam din suma totala pe s[k] nu verificam daca nodul k se afla in subarborele lui j(adica deja il scazusem) sau ceva de genul. La o conditie din asta cred ca gresesti. Vezi sa nu scazi de doua ori aceasi chestie alt caz particular nu e.

Pai la arbori de intervale + hash ma gandeam si eu. Dar cum faci operatia de min-dif ? Poti sa explici putin ideea ca nu ma prind din sursa

Multumesc. Inteleg ca sunteti ocupati. Chestia e ca, asa cum scrisesem si pe topicul problemei, am vazut ca unele persoane au rezolvat-o folosind mai putina memorie si pe pagina cu calibrarea limitelor de timp problema era marcata ca reparata de asta nu stiam daca e din cauza evaluatorului sau de la rezolvarea mea.

E destul de frustrant ca nu primesc macar un raspuns

Se poate sa se mai uite cineva peste problema http://infoarena.ro/problema/eliminare ? Nici cu citirea parsata nu reusesc sa iau vreunul din ultimele 3 teste.

Vezi sa nu scazi aceasi chestie de doua ori sau ceva de genu si fa forurile alea asa

Cod:

for(int i=1;i<=n-2;i++)
   for(int j=i+1;j<=n-1;j++)
     for(int k=j+1;k<=n;k++)

Si eu iau tot 70 cu tle pe ultimele 3. Am vazut ca a fost reportata problema pentru limita de timp si e marcata ca rezolvata. Totusi mi se pare destul de stransa. Am vazut ca si tu Razvan folosesti cam tot 28 de mega pe testele alea. Retii si tu 3 informatii pt fiecare nod din arbore ? Ca sa pot sa elimin elementele am nevoie sa tin un arbore care sa imi zica pe ce pozitie in ordinea initiala se afla maximul de pe un interval. Se poate sa scap de arborele asta ? 

Imi poate spune si mie cineva cum sa folosesc un arbore de intervale pentru operatia min-dif ? 

La lazy propagation ma refeream si eu. Am reusit sa fac ceva ceva pana la urma. Doar ca iau 30 de puncte cu incorect. Imi da bine pe testele de pe site. Am vazut ca au mai fost si altii care au luat incorect tot pe aceleasi teste si apoi au modificat ceva si au luat suta. Probabil e de la long long. Eu zic ca am pus peste tot unde trebuie. E stresant rau ca nu-i dau de cap.


L.E. : Mi-a iesit fix dupa ce am scris mesajul. Nu aveam destul de mari vectorii. Nu inteleg de ce. aveam ceva de genul

Cod:

#define maxn 100005
  long long arb[4*maxn];

De ce nu e de ajuns ?

Imi da si mie cineva un hint la problema asta ? Incerc sa o fac cu arbori de invervale. Problema e ca la fiecare pas am nevoie de minimul pe intervalul [1,N] deci nu mai merge sa folosesc trucul ala sa updatez doar cand e nevoie. Cel putin eu nu imi dau seama cum. Deci cum s-ar face update in log n ?

Ideea e buna. Nu inteleg insa cum verifici daca un subarbore nu apartine altuia. Ai scris execrabil, nu se intelege mai nimic. Explica putin mai detaliat partea asta cu verificarea. Si vezi ca se scrie "iau", fara cratima.


LE : Imi pare rau. Nu pot sa te ajut pentru ca nu imi dau seama daca e bine cum faci tu. Dar pot sa iti spun cum am facut eu. Am facut o parcurgere bfs iar apoi mi-am calculat o matrice a[ i ][ j ] care imi spunea daca nodul j se afla in subarborele cu radacina i. Am calculat-o in O(n logn).

Am incercat sa invat arbori de intervale dar imi e cam greu sa ii inteleg. Voiam sa implementez o sursa in care cresteam valorile dintr-un interval [x,y] cu un anumita valoare iar apoi aveam query suma de pe un interval. Am intrebat pe topicul din arhiva educationala si Mircea Dima mi-a spus despre tehnica lazy update/propagation. Mi-a dat chiar si o sursa demonstrativa. Sincer nu prea am inteles asa ca am cautat pe net dar spre surprinderea mea nu se gasesc chiar asa multe. Ideea cred ca am inteles-o. Adica faci update doar cand e nevoie. De exemplu daca trebuie sa fac update pe [1,10] updatez doar nodul ala si tin o informatie in plus care imi zice ca trebuie sa ii updatez si fii. Cand am query pe un interval mai adanc si dau de un nod din asta il updatez si ii marchez fii. E corect ? Desi nu pare mare filosofie cand vine vorba sa implementez ma incruc rau de tot. De asta as vrea sa vad voi cum implementati. M-ar ajuta mult niste cod. Si inca ceva, daca as vrea query de maxim/minim se modifica cumva functia de update ?

Cum pot face update sa incrementez valorile dintr-un interval [x,y] ? Daca cobor pana in frunze si updatez fiecare interval de lungime 1 presupun ca este ineficient.