Mersi mult, Andrei. Intr-adevar, nu prea m-am gandit profund la problema asta

M-am uitat si eu pe problema... Inca nu am postat-o... Totusi complexitatea nu este O(D * N * N * K)? Adica avem de retinut lungimea, inaltimea maxima, primele K puncte speciale daca au fost bifate si nu mai trebuia sa retinem si inaltimea ultimului punct ( ca sa stim unde ajungem si eventual sa actualizam maxima... )?

 Filip b.

Daca nu reusesti cu dinamica, sa stii ca si backtracking-ul tau poate fi imbunatatit (sa mai iei 10-15 puncte...). De exemplu in stiva de back retii pe fiecare pozitie {0, 1, 2}, adica 0 pentru segment orizontal, 1 - pt. segment care urca, 2 - pt. segment care coboara...
  In plus, ca un caz particular, daca K = 0, se poate rezolva si cu numerele lui Catalan.

  Spor la lucru!  

MII DE SCUZE  :cry: ... cineva in graba caracteristica a uitat sa afiseze n-ul la inceputul fisierului de iesire...  

Hm... Mare pacat ca nu imi da pentru nici un test cu solutie... Oricum, eu o facusem sa imi determine un raspuns indiferent in ce ordine erau scrise numerele la intrare.. Adica nu stiam dinainte ca ordinea era ceva de genul X1 + X2, X1 + X3, X1 + X4, X2 + X3, X2 + X4, X3+X4... Si ca sa aflu X1 pur si simplu calculam (v[1]+v[2]-v[4])/2...

Ok, sorry... O sa-mi caut greseala... Desi iau in continuu 10 pct (doar la testele fara solutie!) iar cu evaluatorul meu imi da impecabil! Nu e nik... Poate imi dau seama ce are ( de nu imi ia NICI MACAR un test cu solutie )...
 
              Filip b.

Am testat cu un evaluator al meu pe teste generate aleator. Merge perfect. Problema e ca programul meu le afiseaza in ordine crescatoare (nu le ordonez dupa, asa le produce algoritmul). Cred ca evaluatorul la problema asta ar trebui schimbat! Doar raspunsurile "2 3 1" si "1 2 3" sunt acelasi lucru...
  Astept comentarii...

  Filip b.

Testele nu sunt publice ( nu ai citit articolele puse mai sus de domino? )... Poate doar daca ai noroc... Succes... Poate iti dai singur seama...


  Filip b.

Si eu am luat 0 la asta(WA la toate).. sunt de abia la prima postare si am cam postat-o pe NV (am dat doar testul din exemplu si inca un test al meu tricky... ). Pentru doua noduri aflam LCA in logN, si apoi pt. fiecare din cele 2 lanturi (de la X la LCA si de la Y la LCA) aflam tot in logN care este minimul pe lantul respectiv cu un algoritm gen cel de la "stramosi", cu intoarcere la descendenti cu puteri de 2. Deci in total pe query imi dadea in final logN ( cu o constanta maricica, e adevarat ).
  Pe langa WA, la testul 10 imi da TLE! Exista si un algoritm mai simplu pt. problema asta?

Unde a revenit?   Iar nu merge.... Hmmm.... Exact cand voiam si eu sa vad daca imi merge LCA-ul....

         bubbleSORT

[in caz ca exista mai multe solutii valide]

Sal... Pai evaluatorul ar trebui sa semene cu cel de la olimpiada ( se gaseste si pe net de download-at parca pe situl cu oji, ca sa vezi un model care sa te ajute ). Este format din unul sau mai multe (2) fisiere BAT si un .EXE care verifica solutia furnizata (in caz ca exista mai multe solutii valide sau chiar daca solutia este unica).
    Si eu vreau sa propun niste probleme (dak mi le accepta   ), dar dupa ce ma intorc de la urmatorul concurs (   )

bubbleSORT

Ms. mult de tot... m-ai scos dintr-o mare dilema... (m-am mai uitat intr-o carte si cc era intr-adevar x1 * y2 - x2 * y1, dar aa si bb erau cu semn schimbat acolo, deci la mine cc TREBUIA CU SEMN SCHIMBAT! )
  ms mult... raman dator  

  bubbleSORT

...

Asa o sa fac...  

Da... m-am prins ce avea... Eu declaram arborele de intervale un vector de lungime 4*NMax - 1, cand de fapt trebuia declarat de lungime 2^K, a.i. 2^K >= 4*NMax-1. De fapt scria si in referatu' de la lot, dar nici nu mi-am dat seama k e f. importanta linia aia si am trecut peste ea fara sa o judec... Avem impresia ca pt un arbore cu X noduri trebuiesc alocate exact X zone de memorie... ca la heap... mi-a luat 3/2 ore sa ma prind...  

Iesea O(N^3) pentru k eu retineam S = suma costurilor nodurilor din subarborele cu radacina in nodul i. Si nu aveam decat de prelucrat (scazut, adunat, etc. ) niste valori S[i1], S[i2], S[i3], S[radacina].
   Oricum, o sa ma gandesc si la chestia cu alegerea doar a doua noduri... (nu prea m-am gandit la asta). ms de sfat.

    O sa postez dupa 27... dak acum evaluatorul e oprit...

deci, postarea dupa data de 27 iunie!!! Si nici macar nu am reusit sa intru in Top20 ( m-am inecat ca tiganul la mal, sunt al 21-lea...  :lol: )

  bubbleSORT

A, de la lot...   si ce treaba are lotul cu asta? Adica ma gandesc ca ei puteau sa lase evaluatorul sa mearga... Nasol... Mda... se pare ca pana se intoarce lumea de la lot eu tre' sa ma pregatesc "manual"  :lol:  :cry:

bubbleSORT

Am si eu o intrebare: de ce se blocheaza cateodata evaluatorul (si da mesaje de genul "asteapta la rand")? Mai ales cand ti-e lumea mai draga...  :lol: oricum, sper ca acum sa "isi revina" repede k sa putem si noi sa mai lucram ceva  :lol:

  bubbleSORT

Sa nu rada nimeni de mine... Poate e banal ( sau poate e clasica ) si nu ma prind (sunt si obosit la ora asta...   ) Daca avem un segment de varfuri (x, y), (x[j], y[j]), toate numere intregi, de ce numarul de puncte laticiale (adik de coordonate intregi) de pe segment este cmmdc(|x-x[i-1]|, |y-y[i-1]|)?  


                                                       bubbleSORT

Da 7655 ( cat ai spus tu ). Daca lucrezi in C/C++, fii atent sa afisezi cu formatul corect... adica nu ai ceva de genul fprintf(fout, "%lld"), si rezultatul tau sa fie tinut intr-o variabila doar de tip long (nu long long). Sau daca ai marcaj de sfarsit de linie (desi nu sunt sigur daca evaluatorul ia asta in considerare)

bubbleSORT

Da... Eu ciclam trei noduri i1, i2, i3, diferite intre ele si diferite de radacina si eliminam muchiile i1-parinte[i1], i2-parinte[i2], i3-parinte[i3]. Fiecare arbore care ramanea in padurea formata era considerat un nod comprimat si facem un nou arbore cu 4 noduri in care prelucram separat fiecare nod... obtineam O(N^3). sper sa imi dau seama ce e...

Problema cere: "Dandu-se un arbore cu N noduri, sa se elimine 3 muchii astfel incat diferenta dintre cea mai mare si cea mai mica suma a costurilor nodurilor din fiecare arbore ramas sa fie minima?" NU? Am testat o gramada... pur si simplu nu vrea sa ia mai mult de 10 pct....

Sorry... nici nu mi-am dat seama k este si o pagina a doua...   Da... dupa ce fac initializarile, in camera cu '*' pun '+'....

Nu merge... chiar nu merge...