Eu sunt pentru mutare. Voi merge la AI-MAS WO duminica, asa ca nu voi participa la runda 2 daca nu se muta.

[Later edit:]

O optimizare este sa observi ca numarul de noduri care trebuie vizitate pentru un query poate fi mai mic.

Presupunem ca dist(x) < dist(y) (altfel se inverseaza x si y).

In primul rand, y si fiecare din copii lui y vor micsora suma distantelor cu dist(y) - dist(x) fiecare. Niciunul din copiii lui y nu trebuie vizitati (trebuie doar sa se calculeze cati copii are fiecare nod din arbore, lucru care se poate face in DFS-ul initial).

Apoi, daca se calculeaza z = LCA(x, y), se observa ca este de ajuns sa se viziteze numai nodurile dintre y si z, mergand pe parinti (care se calculeaza tot in DFS-ul initial). Contributia copiilor nodurilor de pe calea dintre y si z (exceptand copiii care fac parte din cale) se calculeaza ca mai sus.

Cu un LCA banal, se scot 40p. Nu stiu daca un LCA in O(1) ajunge pentru 100p, poate mai trebuie si alte smecherii

Later edit: rationamentul de mai sus e valid, dar LCA-ul e complet inutil (de fapt, nici nu foloseam rezultatul LCA-ului). Trebuie sa fie alta smecherie pt 100p.

Stiu ca a expirat timpul pentru intrebari, dar sigur functioneaza cum trebuie evaluatorul problemei Harta3?

Am observat ca s-a terminat timpul alocat pentru interbari.

Totusi, raspunsul din enunt (434185) este corect pentru exemplu?

Mi-au placut problemele, o incalzire buna pentru Algoritmiada 

Totusi, cand apar in arhiva?

Pe Linux, pe sistemele pe care lucram noi, este aceeasi versiune "optimizata" de fstream care merge mai bine ca libc?

In concluzie: matricea cautata trebuie sa reprezinte un bloc compact din matricea initiala?

O subsecventa a unui sir presupune ca elementele nu sunt neaparat adiacente in sirul initial, dar apar in acceasi ordine ca cea din sirul initial?

Bogdan Tataroiu:
Da, ai dreptate. Pacat totusi ca au fost grupate ultimele teste (cele mari). Asa nu s-a facut diferenta intre cine a rezolvat problema incorect si cine a rezolvat-o incorect si ineficient

Sandu Octav-Emilian:
e tot Greedy, citeste reply-ul meu precedent.

onofrei: ai facut o rezolvare Greedy. Incearca testul:

Cod:

4 2
1 1 1 1

Raspunsul cu algoritmul tau cred ca o sa fie 4 + 3 + 2 = 9, raspunsul corect e 4 + 2 + 2 = 8 (tai in jumatate bucata initiala si apoi fiecare bucata din nou in jumatate).

Intrebarea mea e de ce algoritmul la care m-am gandit si eu si mai multi se pare, pica jumatate din teste...

Daca trimitem mai multe solutii pentru o problema, conteaza numai punctajul de la ultima?
In caz ca o solutie primeste 100 puncte, se mai iau in considerare urmatoarele solutii trimise pentru aceeasi problema?

Multumesc

Da, foarte tari discursurile!

Ar fi bine sa mentionezi si site-ul oficial, care le are pe toate si sunt mai usor de navigat