infoarena

Aici puteti discuta despre problema Deque (http://infoarena.ro/problema/deque).

Am scris o sursa in Pascal (http://infoarena.ro/job_detail/307185?action=view-source (http://infoarena.ro/job_detail/307185?action=view-source)) la aceasta problema si iau doar 60 puncte (TLE la ultimele teste). Pot sa optimizez cumva aceasta sursa sau nu voi reusi sa obtin 100 cu o sursa in Pascal si trebuie sa o scriu in c?  :?

din pacate nici o sursa in pascal nu a reusit sa treaca de 60 http://infoarena.ro/monitor?task=deque&compiler=fpc&score_begin=61

din aceleasi motive ca si la RMQ: http://infoarena.ro/forum/index.php?topic=2823.msg32942#msg32942

Eu nu pot sa inteleg de ce solutia cu deque are complexitate O(N).
Eu m-am gandit la ce complexitate are algoritmul postat aici cu deque si imi iese o complexitate mai mare decat N, insa in nici un caz N.
Pentru ca se parcurge vectorul A o data cu for si apoi se mai parcurge partial si Deque cu un while in la fiecare iteratie in for.
Deci eu zic ca complexitatea trebuie sa fie mai mare decat N.

de exemplu pentru sirul 3 4 1 6 5 cu k=3 se parcurg urmatorii pasii:
se compara:

4 cu 3
1 cu 4
1 cu 3
6 cu 1
5 cu 6
5 cu 1

deci sunt 6 comparari.
Nu rezulta de aici ca complexitatea este 6 (adica N+1) si nu 5 (adica N) pentru exemplul dat?

Nu exista O(N+1)... Gandeste-te ca si cum N ar fi un numar mare si astfel 1 se poate neglija. Nici la O(2*N) nu cred ca se scrie 2-ul. Complexitatea nu arata numarul exact de operatii, ci doar intuitiv, sa poti estima numarul lor.

Puteti citi mai multe despre notatia "O" pentru complexitatea timp: aici (http://en.wikipedia.org/wiki/Big_O_notation) si aici (http://ro.wikipedia.org/wiki/Teoria_complexit%C4%83%C8%9Bii), dar se mai gasesc si multe alte articole pe net sau in carti de specialitate (de exemplu in "Introducere in algoritmi" de Cormen, Lieserson, Rivest, Stein).

Pe scurt, o functie g(n) se afla in clasa O(f(n)), daca exista un ordin n0 (numar natural) si o constanta reala c, astfel incat g(n) <= c*f(n) pentru orice n >= n0. O explicatie mai intuitiva e ca se tine cont doar de termenul care creste cel mai repede si constantele nu sunt luate in calcul. Pe link-urile pe care le-am postat mai sus se afla cate un exemplu.

Aha...deci ar trebui sa analizez mai lejer complexitatea unui algoritm.
Cat despre cele doua linkuri de pa wikipedia pot sa spun doar ca ma depasesc.
Merci oricum!

Cu ce difera sursa mea (http://infoarena.ro/job_detail/546312?action=view-source (http://infoarena.ro/job_detail/546312?action=view-source)) cu cea a lui Rares
(http://infoarena.ro/job_detail/545858?action=view-source (http://infoarena.ro/job_detail/545858?action=view-source)).
Mi-am modificat sursa pana a ajuns aproape identica. Dc iau 25 si el 100?

Din cauza citirii, tu ai "%i", ceea ce se folosea mai demult in borland ( daca nu ma insel ) . Incearca sa folosesti "%d", si o sa mearga, si la rezultat sa folosesti "%lld", uite aici sursa ta : http://infoarena.ro/job_detail/546327
[LE] Totusi "%i" cred ca mergea, greseala fatala era la rezultat, trebuie "%lld" ..... dar folosesti "%d" mai bine alte dati :D

Mersi

Dar cred ca fiindca lipsea ll-ul de la format.
http://cplusplus.com/reference/clibrary/cstdio/printf/ (http://cplusplus.com/reference/clibrary/cstdio/printf/)
Scrie acolo d or i pt Signed decimal integer.
Mie-mi place mai mult cu i.

_________________________________
http://infoarena.ro/job_detail/547479 (http://infoarena.ro/job_detail/547479)
http://infoarena.ro/job_detail/547484 (http://infoarena.ro/job_detail/547484)

Se pare ca e mai lent cu %i.
din ce am inteles pana cum
++i mai rapid ca i++
%d mai rapid ca %i
max-ul de mana mai rapid decat cel din stl
streamuri mai rapide pe infoarena, scanf si printf mai rapide pe campion si la olimpiada.

Atata timp cat implementezi calumea nu ar trebui sa fie problema detalii de genul.

http://infoarena.ro/job_detail/547479 (http://infoarena.ro/job_detail/547479)
http://infoarena.ro/job_detail/547484 (http://infoarena.ro/job_detail/547484)
Pe infoarena iau 60 cu %i si 100 cu %d.

Se pare ca unele teste sunt mai rapide cu %i, altele cu %d. Iar unul dintre ele iese de tot din timp la %i.

Au mai fost unele de 90 cu scanf si 100 cu streamuri.
Poate ar trebui marite un pic limitele, nu stiu.
Oricum, daca zici ca la olimpiada nu conteaza e bine. Poate sunt mai mari limitele.

Faza cu ++i, i++ conteaza de la caz la caz. Daca ai V[++i] sau V[i++] sunt doua lucruri diferite. Si in for, nu conteaza cum il scrii, fiecare cum s-a obisnuit. Streamurile in general merg mai repede, pentru ca sunt mai noi si s-au dezolvata mai bine ca si printf, dar uneori citirea din c face minuni. Si da, "%d" e mai rapid ca si "%i" pentru ca formatul "%d" e mai nou.

Stiu ca v[++i] sau v[i++] sunt doua chestii diferite.

De ce depasesc timpul la sursa asta (http://infoarena.ro/job_detail/632679?action=view-source). Am incercat s-o fac cat mai rapida dar pe pc-ul meu doar citirea la testul 15 imi ia ~1.4 secunde deci nu vad cum ar incapea in timp (am incercat si cu deque din stl si cu vector simplu dar iau la fel).

Cineva de pe infoarena zicea ca s-au micsorat timpii la unele probleme. Nu am inteles care e treaba. Dar vad ca nu se mai ia 100 nici la deque, nici la componente tare conexe de o saptamana ...

Am crescut limita de timp si am reevaluat problema.

Multumesc! :ok:

Si problema http://infoarena.ro/problema/secvdist se rezolva tot cu ajutorul deque.

hmm iau TLE pe ultimu test cu heapuri dar nustiu cred ca greseste ceva pt ca pe penultimu test am 2sec ..nu pot deschide testul 20 nici cu notepad nici cu word ..

Iei TLE pt ca folosesti heapuri si nu deque.
Desi nu e frumos sa storci niste puncte pe o complexitate de O(NlogK) in loc de O(N) poti incerca parsarea numerelor din input.
PS: Nu incurajez obtinerea de puncte multe pe complexitati mai mari decat ar trebui. :)

 :D nu fac probleme pt puncte  dar doar ziceam ca nu cred ca e de la program o sa incerc sa parsez ,cred ca are ceva mai special ultimu test;
PS:Am fost la oni iti mai amintesti de mine?eu eram ala muci: :rotfl:

Da, da, da. Cum sa nu imi amintesc? :))

De ce iau sigsegv pe asta ? http://infoarena.ro/job_detail/807054
Bag direct elementul in deque in loc de pozitia lui, in rest e la fel ca sursa de 100.

Scapi de kbs daca faci if (i - k >= 1 && deque[front] == a[i - k]), am inversat conditiile. Ramane sa scapi de incorect.

Incorectul il iei din cauza ca bagi in deque valoarea elementului si nu pozitia lui. Asta e gresit in conditiile in care 2 elemente se pot repeta, deci tu poti scoate front-ul inainte sa fie cazul. Problema e la linia asta:

if (deque[front] == a[i - k] && i - k >= 1)

PS exemplu mai bun: sa presupunem ca a[i - k] nu e primul element din deque la momentul i, dar va deveni la un moment j, j > i. Astfel nu il vei scoate niciodata din deque.

Stiu ca trebuia sa iau incorect tocmai cum ai zis tu, dar nu stiam de ce kbs. Prima data am trimis cu if (deque[front] == a[i - k]) si a doua oara am pus si (i - k >= 1) si tot luam kbs, dar mi-am dat seama acum de ce, degeaba puneam conditia cu i - k >= 1 dupa ca el oricum evalua mai intai a[i - k]. Mersi de explicatii.

O alta problema ce se rezolva cu deque este Secvdist  http://www.infoarena.ro/problema/secvdist

Cred ca testele sau timpul de executie ar trebui putin revizuite. Nu de alta, dar cu heap se poate lua suta fara niciun fel de optimizari :)