Sau ai putea sa ne spui cum faci... in concurs nu-ti da nimeni testele...

Poti sa faci fara sa te complici cu pointeri, cu un singur vector, sa zicem un vector A.

A[1] va fi radacina, A[2] si A[3] vor fi fiii.

In caz general, fiii unui nod A[k] sunt A[2*k] si A[2*k + 1]. Parintele unui nod A[k] e A[k/2]. Mai multe detalii gasesti aici: http://en.wikipedia.org/wiki/Binary_tree

A fost foarte fain! Mult succes la IOI

Foarte tari problemele... va aparea articol cu solutii sau abia dupa ultima runda?

  Nu-mi vine sa cred... a intrat in 5.5 sec pe ultimul test 

Puteam sa jur ca folosind structuri va fi cu mult mai incet...

Mersi mult pentru ajutor

Ok, mersi, aproape ca mi-a iesit!

Am TLE pe ultimele 2 teste... si am optimizat cat am stiut. Am doua interogari pentru a afla a x-a si a y-a pozitie neeliminata, apoi una pt a afla maximul si apoi o actualizare. Ceva idei de optimizare? In afara de a parsa citirea nu prea mai stiu ce sa fac...

Si cum as putea face asta?

Eu m-am gandit sa aflu cate elemente au fost eliminate in intervalul [1, x] si [1, y] cu un arbore, si apoi query-ul pt maxim sa-l fac in intervalul [x+eliminate_in1-x, y+eliminate_in1-y]... dar asa si pe cele 2 teste care intra in timp iau WA, deci nu e bine...

Cum ar trebui sa fac query-urile in arborele de intervale astfel incat sa tin cont de elementele sterse (notate cu -1)? Mai exact, cum imi dau seama in ce interval trebuie sa fac query?

Am vazut ca solutia oficiala tot asa sterge elementele... dar codul este scris astfel incat nu se poate intelege mare lucru din el

Cred ca am inteles acuma despre ce-i vorba, sper sa ma descurc mai departe.

Multumesc!

Dap, a mers de 100! Mersi inca o data, nu-mi dadeam seama cum sa aplic memoizarea aici... 

Mi-ati putea explica mai exact un pic cum trebuie folosita memoizarea la problema asta? Eu am o matrice b, unde b[ i][j] = lungimea maxima pana in punctul [i,j]... si calculez matricea asta recursiv, dar iese din timp pe testul 4. Pe un test cu structura celui dat de filipb, se fac intr-adevar foarte multe apeluri recursive, mult mai multe decat n^2.

Stiu ca memoizarea se poate folosi in calcularea functiei fibonacci, de exemplu, pentru a evita recalcularea de mai multe ori a aceleiasi valori in apeluri recursive. Aici insa eu nu vad cum m-as putea folosi de tehnica asta...

Pai fac bellman ford..

Adica bag un nod in coada de fiecare data cand ii pot imbunatati costul, daca nu se afla deja in coada, si daca pot ajunge la el cu energia ramasa. Astfel, fiecare nod poate sa fie in coada de maxim n ori.

Chiar daca se blocheaza a doua varianta, pentru un w mai mare tot voi avea posibilitatea sa merg pe primul drum... desi asta numai daca costul energetic al unei deplasari nu este mai mare decat k

Daca este... da, cred ca as pica pe un asemenea test...

Eu nu am facut cu matrice... eu tin doi vectori d si en, d[ i] = distanta minima pana in nodul i ( daca nu se poate ajunge cu o lanterna de valoare w, atunci este infinit ) si en[ i] = energia ajunsa pana in nodul i. Cand vreau sa expandez un nod din coada, ma folosesc de vectorii astia...

O sa incerc s-o fac si cu matrice, vad ca nu vrea nicicum cum m-am gandit eu...

Eu inca nici nu am implementat cautarea binara, caut liniar lanterna, si totusi WA pe testul 9.

Daca afisez k si distanta returnata de Bellman Ford cu k iau 0 deci nu cred ca-i de la asta.

Mi-ai putea spune cum ai verificat daca poti ajunge din nodul 1 in nodul n cu o anumita lanterna?

Imi dati va rog o idee pentru testul 9?

Am facut bellman ford cu coada. Cand scot un nod p din coada, adaug orice nod q legat de p doar daca en[p->nod] ( energia ajunsa in p pana in acel moment ) + q->en ( energia necesara parcurgerii ) <= w ( energia maxima pentru care caut distanta minima )..

Mai poate sa iti cicleze cautarea binara. Daca faci cautare binara in intervalul [a, b], si ai ceva de genu while ( a <= b ), a poate sa nu-l depaseasca niciodata pe b pe unele cazuri, si atunci iti va cicla. Poti rezolva asta ori punand un break daca se intampla asta, ori avand grija la cum modifici valorile a si b astfel incat sa nu se intample chestia asta...

Mie imi da 5 4 3 4 cu sursa de 100... care-i raspunsul pana la urma?

1 1 3 4 eu zic ca sigur nu-i corect. De la nodul 1 pana la 2 sunt clar mai multe drumuri ( 1 - 2, 1 - 4 - 2, 1 - 5 - 4 - 2, 1 - 5 - 4 - 3 - 2, 1 - 4 - 3 - 2, daca am facut bine )

Nici mie nu imi da bine pentru celelalte noduri.. oricum nu cred ca are importanta, ca se precizeaza ca nu poate exista un cost mai mic ca 2.

Multumesc, mi-a iesit! 

Imi dati va rog un indiciu pt teste 1 5 si 10? Iau TLE.. si nu prea stiu cum sa scap de el..

Aflu pentru fiecare numar in cati pasi ajunge pe pozitia finala, avand un while care il intoarce pe p1[p1[p1[...]]]... si apoi fac cmmmc al acestor numere. Si daca scot cmmmc-ul, tot da TLE pe testele alea. Am incercat sa tratez particular cazul 2 3 4 ... n 1 dar tot nu vrea...

Cum as putea face mai eficient? 

Apelul initial se face de fiecare data cand scoti un element din coada si vrei sa-l expandezi.

Eu parca am folosit ~14 mega pe ultimul test. Ideea a fost sa am o functie recursiva care sa ma "scoata" din zonele cu acelasi numar pe ele, fara a le mai baga din nou in coada. Poate te ajuta asta.

Alta ideea ar fi sa faci coada dinamica, sub forma de lista inlantuita. Daca p e inceputul, cand mergi in p->next, il stergi pe p. Nu stiu daca te ajuta la problema asta... mie mi-a mers cu coada facuta pe vector si functie recursiva asa ca nu am mai implementat si asa.

Nu ar trebui completat articolul cu solutii?

pai si daca am:

2 2
2 3
2 4

cum mai consider ca sunt opuse? 
probabil ca-i asa cum spui, n-am rezolvat inca problema, dar nu prea e logic...

in exemplu, strazile sunt:

5 6
2 2 (1)
0 3
2 7 (2)

distanta dintre orasele de la capatul strazilor (1) si (2), care este? 7+2 = 9, sau 7-2 = 5? Se pot suprapune strazile?

N-am citit cu atentie  cred ca mi-am dat seama acuma, mersi..

Eu nu inteleg cum sta treaba cu acele conditii pentru ca un etaj sa fie liber sau ocupat...

daca anul trecut etajul curent si etajul de dedesubt au fost ocupate, atunci etajul va fi liber anul acesta
...

Anul trecut etajul curent nu exista... nu? Daca in fiecare an se adauga un etaj, in anul X-1, etajul X nu exista. Vrea sa spuna cumva "ultimul etaj" sau ce?