014 Secventa

[•vladcyb1]

Hai ma ca nu e nici o problema nicaieri. Evaluatorul merge bine, dar trebuie sa te obisnuiesti cu timpi afisati de el. Optimizeaza programul si nu o sa mai ai nici o problema, o sa ia 100 imediat.  

[•wickedman]

Timpii de execuţie sunt orientativi. Te ajută să testezi optimizări şi algoritmi.
Cronometrarea la evaluare funcţionează altfel.
Cât despre diferenţa medie ...

[•Dorin]

asta este altceva
o cu totul alata explicatie   mersi am luat in cele din urma 100 pe aceasi sursa am mai trimis-o de doua ori shi 100 p

[•gogu]

Cred ca trebuiau facute niste teste putin mai dificile.
Un brute force O(N*K) la care mai adaugi 2-3 linii ia 100 p, deoarece pe cazuri generate random se comporta cam ca un O(N).

[vladut.forum]

ok ,care a luat 100 la problema asta sa imi bage si mie niste teste, ca eu iau numa WA...testele nu iau tle ci doar wa, si rog pe careva care a rezolvat problema sa imi lase si mie niste teste ... thanks

[•cos_min]

care da nishte exemple care o luat 100 de pcte, k io nush dc iau 0 pcte(tle+wa) pe pr .... plz plz  

[u-92]

descrie un pic ce faci, acolo e greseala..
p.s.: ai citit posturile de mai sus? sunt cateva idei bune de rezolvare

[•andreisfrent]

  a incercat cineva pana acum divide et impera? oare se poate folosi?

[•filipb]

O abordare divide et impera implica cel putin o complexitate O(N log N), iar daca vrei O(N log N) merge simplu si fara complicatii cu arbori de intervale sau orice alta structura ce executa operatia de minim pe o subsecventa in O(log N). Dar aici limita de timp este f. stransa tocmai pentru a face o departajare intre un O(N) - rezolvarea optima - si un O(N log N). 

[johnyd]

Cum se optimizeaza de la 90 -> 100 p ?
Testul 10 imi da in 0.20 / 0.21 sec
Care e smenul aici?

 Multumesc, daca imi rapsunde cineva!

[Tabara Mihai]

Cum se optimizeaza de la 90 -> 100 p ?
Testul 10 imi da in 0.20 / 0.21 sec
Care e smenul aici?

 Multumesc, daca imi rapsunde cineva!

mai trimite odata solutia ca poate iei 100.Am mai patit faze din astea pe la alte probleme.

[•pauldb]

Poti sa parsezi citirea, daca chiar nu merge nimic altceva.

[•amadaeus]

Iau TLE pe ultimele doua teste pe solutia O(n). Am incercat atat implementarea C, cu citire standard si deque implementat pe vector, cat si C++, cu deque din STL.
Care ar putea fi problema? 

[•filipb]

Fa deque in felul urmator:

Cod:

		while (first <= last && Q[first].poz <= i-k) first++;
		while (last >= first && Q[last].V >= v[i])   last--;

si incearca sa parsezi citirea. Mie mi-a intrat asa.

[•amadaeus]

Asa facusem deque de prima data.
Citirea o fac

Cod:

scanf( "%d", &x );

Si.. TLE pe ultimele 2 teste. Nu vad ce as putea imbunatati, cu exceptia citirii.
Cum se poate face mai eficient?

[•astronomy]

Faci ceva de genul:

Cod:

int ind, x;
char sir[1024];
fgets(sir, 1024, stdin), x = ind = 0;
for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
    x = x*10+(sir[ind]-'0');

Cam asta inseamna sa parsezi citirea, citesti ca un string si apoi transformi in numere. Cand volumul datelor de intrare e foarte mare, se simte diferenta de timp.

[•amadaeus]

Da, am parsat citirea si a intrat lejer in timp.
Cu toate astea, o mica obiectie pt problema: limitele de timp ar trebui puse, dupa parerea mea, in asa fel incat un algoritm de complexitate optima sa poata lua max fara sa fie nevoie de citiri "dubioase" .
Pareri?

[•fireatmyself]

eu n-am parsat citirea si mi-a intrat in timp 

[•k_ounu_eddy]

Unde pot sa gasesc rezolvarea de la problema Trans?

[•astronomy]

O gasesti la sectiunea downloads pe infoarena, oni 2004.

[•k_ounu_eddy]

Ar trebui mai intai sa ma uit mai atent sa vad despre ce e vorba in trans,sa o inteleg pe aia,si apoi sa fac si problema asta.Dati un indiciu,nu vreau rezolvarea completa.Deci introduc primele k numere in stiva(acolo zicea ca e o coada),si apoi iau pe rand ,restul numerelor le inserez in stiva,si cele care sunt mai mari decat noul numar ,le elimin din coada,sau cum?Am facut asa si nu imi iese.De exemplu am sirul 54321 ,si k=3;
pun primele 3,si stiva arata 543;iau 2-ul,si apoi elimin si 5 si 4 si 3(ca sunt mai mare ca 2),si tot asa pana la sfarsit,cand raman cu 1.Si vad ca nu mia dat raspunsul corect.

[•pocaitu]

  pe exemplul tau , la inceput stiva arata 3 .poate ai uitat sa retii intr-un vector pos[ i ] pozitia elementului i din stiva in sirul initial . Si daca ajuntgi ca i-pos[inc]>k elimini acel element(faci inc++) . La inceput inc=1  

[•mocke]

Ca sa mearga mai repede tin minte ca eu am setat un bufer de o anumita dimensiune, ca sa se produca citirea mai repede.    Puteti sa va uitati in sintaxa de C++ la "setbuf" si sa testati si metoda asta.

[•k_ounu_eddy]

Am inteles cum sta treaba.Acum sa vad de ce primes SIGSEGV  .Pe compilatorul meu(tot Gnu C++),nu primesc eroare,dar nu am Linux(iar signal 11 apare doar pe Linux,din cate stiu).

[•k_ounu_eddy]

Poate cineva sa imi explice de ce iau SIGSEGV,ca nu ma prind