210 Minim

[ditzone]

Aici puteţi discuta despre problema Minim.

[nivan]

 Eu fac in O(n^2) cautarea secventei. Adica cu sume partiale. Iau doar 90 pct. Cica TLE la ultimul test. Exista o complexitate mai mica?

[andreit1]

O(N*nr_eliminari) ( adica O(N^2) pe cel mai defavorabil caz)este suficient pentru a obtine 100 puncte.

[nivan]

 hm.... mie imi ia TLE la ultimul test. 

[•Cosmin]

Tu ai O(n^3) in general ... nu O(n^2).

[•cos_min]

cat va da pe:

9

6 -8 -2 -4 -6 -10 -3 12 -12

later: am obtinut 90, wa pe ultimu test

[•tm_radu]

cat va da pe:
9
6 -8 -2 -4 -6 -10 -3 12 -12

mie mi-a dat:

Cod:

-33 2 7
-12 9 9
6 1 1
12 8 8

[•gabitzish1]

cei care ati luat TLE pe ultimul test.. cum ati optimizat'o?

[•Florian]

Pai..nu sunt in situatia lor insa trebuie tinut seama de urmatoarele:
*nu e nevoie de eliminarea elementelor ci doar de marcarea celor care ar trebui eliminate..
*suma minima ar trebui sa se obtina o(n) (liniara) pt fiecare parcurgere...
Cam atat trebuie...vezi poate iti intra in vreo bucla infonita sau ceva de genu... 

[•gabitzish1]

Sunt tare descurajat in legatura cu problema asta  .. primele 9 teste imi ies cu 0 ms iar la ultimul iau TLE.. nu'mi dau seama unde gresesc, sau ce mai trebuie sa optimizez....

[•hulparuadrian]

In legatura cu ultimul test...numere din fisier sunt 0 toate (credeti-ma pe cuvant!).Mi-am dat un test cu n=10 si numerele toate egale cu 0 si greseam. Acum iau 100, dar inainte luam WA pe testul 10. Sper sa va fi fost de ajutor...si imi cer scuze daca gresesc. 

[•bodyionita]

Rezolvarea este relativ simpla... editat

Editat de moderator: Lasa'i si pe altii sa se gandeasca la rezolvare.

[•dariusdarius]

Ce ar trebui sa dea la testul: 10   0 0 0 0 0 0 0 0 0 0  ?
asa ceva:

0 1 1
0 2 2
0 3 3
0 4 4
0 5 5
0 6 6
0 7 7
0 8 8
0 9 9
0 10 10

nu?

[•SebiSebi]

Da, asa trebuie sa dea.

[•timics]

Ma bag si eu in seama inainte de a rezolva problema, sa spun ca se zice "indicele de inceput mai mic", nu "indicele de inceput mai mica"

[•klamathix]

Avem licenta poetica. Dar ce zici, se zice ora "doi" sau ora doua?

[•timics]

e mai logic "doi" din pacate )

[•DorelBarbu]

Daca eliminam o subsecventa, trebuie sa decalam elementele spre stanga? Ceea ce vreau sa spun este: pe exemplul nostru ,daca eliminam prima seventa (intre indicii 2 si 5), spatiul gol lasa de aceasta va fi ocupat de elementele aflate dupa pozitia 5? Vom mai putea avea o seceventa de lungime mai mare ca 1 care sa il cuprinda si pe 6, sau nu?

[•Vasile_Catana]

conteaza in ce ordine le afisam ?

[•dragangabriel]

Da, conteaza. Tripletele se vor sorta in functie de suma minima. Daca se gasesc triplete cu aceeasi suma minima se vor sorta in functie de lungimea minina (indice final-indice initial). Daca se gasesc, din nou, triplete cu aceeasi lungime minima se vor sorta dupa indicele de inceput. Bafta !

[•Vasile_Catana]

tot nu-mi iese 

[•nimic]

Buna ziua,
Iau 90 cu Wa pe ultimul test, am incercat multe teste, printre care si cel doar cu 0....si toate cu mers, s-ar putea uita cineva pe sursa mea?
Multumesc anticipat.

[•lucametehau]

Cum se calculeaza subsecventa de suma minima?? 

[•Bodo171]

Cum se calculeaza subsecventa de suma minima??  

Te poti folosi de algoritmii de aici: http://www.infoarena.ro/problema/ssm ,trebuie doar sa schimbi unele conditii ca sa obtii minim,nu maxim.

[•lucametehau]

Multumesc