infoarena

Aici puteti discuta despre problema Subsecventa de suma maxima (http://infoarena.ro/problema/ssm) din Arhiva educationala (http://infoarena.ro/arhiva-educationala).

E cam ciudat ca sursa asta (http://infoarena.ro/job_detail/261099?action=view-source) ia TLE pe testul 19. Rezolvarea e O(N) ca timp si O(1) ca memorie. E din cauza citirii ?  :?

Da, problema e de la funcțiile folosite pentru citire. Când am evaluat, surse cu scanf() mergeau uneori cu 0.3s mai rapid pe un test la a doua rulare. Nu știu de ce se întâmplă așa. Dacă retrimiți sursa cred că vei lua 100 de puncte. Ciudat lucru, dar nu am ce-i face.

Dacă în schimb vei folosi streamurile din C++ nu vei avea nicio problemă. Succes!

Florian, iată: 100 cu sursa ta și 2s maxim pe test (http://infoarena.ro/job_detail/261125). :)

Streamurile nu erau mai incete?  :?

Acum sunt mai rapide. :)

Ciudat... cu streamuri iau 70 (http://infoarena.ro/job_detail/261153)

Iar eu iau 100 așa (http://infoarena.ro/job_detail/261155).

Adica el citeste mai greu daca deschid fisieru' cu freopen?

Ce urat sa patesti o faza de asta intr-un concurs.  :)

Așa se pare.

Mi s-a parut foarte interesanta metoda formarii sirului unui vector de lungime foarte mare la problema:
http://infoarena.ro/problema/secv6
Cred ca s-ar putea implementa ceva asemanator si aici, astfel incat sa nu mai fie probleme cu citirea.

Cred ca ar trebui un test in care toate numerele din sir sa fie negative. Eu iau 100 ignorand acest aspect(obtin rasp 0 in loc de maximul din acel sir);

Vor fi taxați și cei care inițializează suma maximă cu 0. :)

Nu inteleg un lucru: Streamurile merg mai repede acum pe aceasta problema sau in mod general mai repede decat cu citire in C? Eu credeam ca streamurile merg in general mai greu si chiar am patit-o la cateva probleme cu backtracking sa nu mearga varianta cu streamuri.
Daca poate cineva sa-mi explice as fi recunoscator. :)

Pe infoarena, înainte streamurile mergeau mai greu decât citirea în C. Dar, de ceva timp, deoarece s-a făcut un update, sunt mai rapide. Pe alte siteuri, streamurile sunt în continuare mai lente.

Mersi pentru raspuns  :ok: , acum sa fac problema cu streamuri sa vedem ce iese.

Anul trecut la ONI/baraje/lot streamurile erau mai lente. E mai sigur sa citesti in C :).

nu vreau sa sune prea critic, dar la o problema din arhiva educationala credeti ca e normal ca diferenta sa se faca la citirea cu streamuri si modul de deschidere al fisierului?

Nu este intentia noastra sa nu poti lua 100 cu streamuri, dar uite care e problema:

- vrem ca o citire normala in C (scanf) + algoritm O(N) sa ia 100
- vrem ca o citire parsata in C (fgets) + algoritm O(N log N) sa ia mai putin de 100
- vrem ca o citire normala in C++ (streamuri) + algoritm O(N) sa ia 100

Din pacate streamurile merg (mergeau) atat de prost incat nu puteam sa dam limita destul de mare, pentru ca ar fi intrat o solutie parsata proasta in C :).

Si in orice caz, este mult mai bine sa va chinuiti pe infoarena si sa va invatati sa cititi cu scanf, decat sa pierdeti puncte din aceasta cauza la olimpiada si sa va dati cu capul de pereti ;)

am inteles  :ok:... incurcate sunt caile compilatoarelor... e bine de stiut insa ca la majoritatea concursurilor inca sunt mai rapide citirile in C :)

@wefgef - se putea da inputul printr-o formula. Si mie mi se pare putin aiurea sincer sa fiu sa te chinui atata sa optimizezi o problema din arhiva educationala.

La ce chinuri te referi? Problema scanfurilor e că funcționează uneori cu 0.2, 0.3s mai lent pe testele mari. Cei care s-au plâns că nu au luat 100 cu scanfuri eu le-am retrimis sursa și am obținut 100 lejer.

Scopul arhivei educationale e sa aprofundeze un algoritm si nu sa ne abatem de la subiect pe metode de generare ale inputului. Se poate lua usor 100 si folosind printf/scanf, trebuie doar sa folosesti O(N) timp si O(1) memorie, adica solutia optima.

cu aceeasi sursa, si anume asta (http://infoarena.ro/job_detail/267426?action=view-source) am luat pe rand 80, 90, 95, etc.
LE: nvm, am reusit.

Punctajul nu era 100 pentru că nu aveai memorie O(1).

iau 95 de puncte pentru ca am rezultat incorect la a doua rulare

datele de intrare sunt:
15
-1 7 5 0 -7 -9 0 8 -2 5 -2 1 4 9 1

si rezultatul programului meu:
24 8 15

ce nu este in regula?

Daca ai mai multe subsecvente cu aceeasi suma, trebuie afisata cea cu indicele de inceput mai mic. Tu mai ai un 0 pe pozitia 7, pe care daca il adaugi la subsecventa iti da aceeasi suma, dar indice mai mic.
Raspunsul e 24 7 15.

da eu am inteles exact inversul din enunt. iti multumesc :D o sa modific acum

Am si eu o intrebare... ce ar trebui adaugat la o sursa care merge in O(n) (sper  :?) http://infoarena.ro/job_detail/279341?action=view-source (http://infoarena.ro/job_detail/279341?action=view-source) ca sa aleaga subsecventa care are minim k elemente?  :ok:

Inca o conditie... if (poz_final- poz_inceput + 1 >= k)

L.E. : My bad... m'am grabit.

Am impresia ca asa, risti sa nu iti gaseasca nicio secventa. Cred ca e nevoie de un deque (http://infoarena.ro/problema/deque). Gresesc?  :-k

LE: De exemplu, daca toate elementele sunt negative, nu merge. [ ca lungimea sumei curente va fi mereu 1]

Nu gresesti. Nu e de ajuns acea conditie. Daca ai numai elemente negative spre exemplu nu o sa iti gaseasca nimic. Nu cred ca e nevoie de deque, cred ca e de ajuns un minim.

bun si in concluzie daca merg cu un k si in mom in care suma devine negativa il resetez nu merge...
cum ar trebui sa fac ca sa ia si cazul in care spre ex am :
(n k si numerele)
la asta raspunsul ar trebui sa fie -14 1 4 .. ce ar trebui sa adaug ?  ](*,) 

Ar trebui sa ai variabila pentru solutie initializata cu maximul dintre numerele din vector.

@catalin93: Solutia ta nu se poate adapta pentru a gasi subsecventa de suma maxima de lungime cel putin K. Trebuie sa folosesti o solutie ce are complexitatea de memorie O(N) (sau O(K), daca vrei sa optimizezi memoria).

pana la urma cu ce ar trebui sa citim/afisam, ca sa fie timpul cat mai scurt? ... cu streamuri sau cu scanf() / printf() ?

Pe calculatoarele actuale nu prea conteaza,in general nu se face diferenta pe citire ci pe eficienta.

Nu intzeleg dc numi  ia primele 3 teste... is cele mai mici... atzi putea sami spunetzi ce caz special au... nu pot sami dau seama dc nu le iau:D

Banuiesc ca nu verifici initial daca toate valorile sunt negative.

MSM unu din cazurile pe care le scapa asta era... la celelalte 2 teste am fost eu banana...:)) la mine daca subsecventza se termina pe ultima pozitzie nu mai facea testul sa vada daca nu cumva secventza care se termina acolo e cea mai mare... oricum mersi mult:-*

 :harhar: foarte dragut... pentru o sursa pe care am luat 100 :D acum am luat 90 dupa care 85 .. dupa caree 80 :?.. faza e ca pe unele teste. ia 2,19.. deci nu depaseste 2,2... :fighting:

am si eu o problema.. pe o sursa de complexitate O(n) cu citirea facuta in <stdio.h> iau 95.. de ce?.. iau tle pe ultimu test..   :-k ceva e dubios

cum se poate sa iau 90 pe aceeasi sursa pe care acum 10 min luam 95?
repet.. citirea e facuta cu scanf..
spuneti-mi pls macar sa nu fiu ca in bancul cu nebunul de pe autostrada..

S-a mai vorbit de asta pe forum. Ai o sursa ce e la limita si uneori intra, alteori nu.  :)

1.shi in caz de concurs ce as face?
2.daca exista o metoda mai putin complexa decat asta pls tell me.. :eyebrow:

Pe compilatorul de pe infoarena, din ce am retinut, sunt mai rapide streamurile. Schimba la streamuri sa vezi daca mai ai probleme cu incadrarea in timp.  :peacefingers:

E cam stransa limita de timp. Adica, eu ar zic ca ar trebui sa intre si cu scanf, ca doar e problema din arhiva educationala. Deci, daca ati putea mari limita de timp astfel incat sa intre O(N) cu scanf, si sa nu intre o solutie de complexitate mai mare, ar fi ok, dupa parerea mea.  :thumbup:

Intra in O(n) si cu scanf/printf :)

Cat da pe testul   " 4 
                           4 11 -10 1" ?
 

15 1 2

Ok mersi.
L.E : Mi se pare sau ultimile 3 surse oficiale  de 100 sunt gresite. Pe testul   Imi afiseaza gresit inceputul secventei.

Trebuie să fie iniţializată variabila idx: în prima sursă cu 0, iar în celelalte 2 - cu 1.

Nu modifica nimeni sursele?

Eu am luat 100 pe ea, dar pe pagina problemei la scorul in arhiva imi scrie N/A.

In arhiva educationala, tot timpul la scor vei avea N/A, indiferent de scorul obtinut. Probabil e un bug ... sau nu s-au ocupat de asta adminii. Oricum cred ca o sa se rezolve in IA3.

Primesc incorect la testul 3 4 si 10 si nu-mi zice daca am gresit la suma sau la indici, e ceva mai special la acele teste?

Iti poti descarca testele , atat in-urile cat si out-urile de la atasamente si poti vedea singur ce e gresit.

In testul #3 este o greseala in fisierul de intrare "20-20", din aceasta cauza si primim "Raspuns gresit"

testele sunt corecte :)...vezi sa ai grija la restrictii...acolo m-am incurcat si eu prima data :D

E un rand nou intre ele, dar probabil editorul tau de texte nu il afiseaza.

Intr-adevar. Era o problema cu editorul meu de texte. Multumesc

de ce nu merge main-ul? :@

Pai...poate pentru ca in este si variabila si nume de fisier?...calculatorul saracu' nu stie cu ce in sa citeasca ...
Mai ai o greseala mare: s nu e initializat...si mai multe
Apropo solutia optima nu e O(N²) ceea ce ai tu ci O(N)

Ce au special testele 3,4 si 10?
Nu inteleg ce gresesc...
Se poate uita cineva pe sursa mea, va rog?
http://www.infoarena.ro/job_detail/964782?action=view-source (http://www.infoarena.ro/job_detail/964782?action=view-source)

Nu este corect sa pui in else si conditia pentru suma maxima. Tu pierzi testele in care subsecventa de suma maxima are doar un singur element.   :ok:

Aha..m-am prins, am sa incerc sa implementez ceva maine (adica azi :D )...
Multumesc mult!!  :thumbup:

EDIT:Bun...am incercat sa modific programul a.i. sa aiba complexitate O(n) si sa nu-mi mai dea WA la testele 3,4 si 10.
Dupa cateva incercari am zis sa apelez la 'BF' (brute force) si sa mai fac o parcurgere la sf programului (O(2*n)) a.i. sa-mi gaseasca, daca exista, o subsecventa de la lungime 1 care sa fie maxima...n-a mers...tot primesc WA pe 3,4 si 10.
Alte idei???  ](*,) ](*,) ](*,)

Parcurgerea de la sfarsit defapt nu iti parcurge sirul :) Nu folosesti nicaieri s[i].

Mda...neatentia.
Mersi!  =D&gt;

EDIT:Am mai crescut cu 5 puncte :D ... testele 4 si 10 tot nu merg :-?

Pica pentru ca afisezi capatul stang gresit! Gandeste-te la urmatorul caz : gasesti cea mai buna secventa pe intervalul [5, 10]; iar apoi pe la pasul 15 gasesti sum < 0 si faci sum = a[ i ] iar st = i; in continuare cea mai buna secventa e aia de pe [5, 10] la pasul 16 te opresti si tu afisezi suma de pe [5,10] 15, 10; ceea ce e gresit :).

Am luat 100 dar am gasit un exemplu care imi afiseaza gresit :))

http://www.infoarena.ro/job_detail/257846?action=view-source (http://www.infoarena.ro/job_detail/257846?action=view-source) e putin gresita  :fighting: daca toate numerele sunt pozitive , idx nu va fi setat bine.

Primul link nu mai merge

In solutia cu programare dinamica variabila idx trebuie initializata cu 1 in cazul in care subsecventa incepe chiar de pe prima pozitie ;)

Imi poate spune cineva de ce nu iau nici un test?
Atunci cand rulez testele pe PC-ul meu, raspunsurile sunt corecte (pana la testul 17 am verificat).
Insa evaluatorul infoarena imi da 0 puncte.

Poate sa imi spuna cineva de ce nu am rezultatul bun la testul 2?

Nu selectezi subsecventa cu indicele de inceput cel mai mic. De exemplu pe testul:
raspunsul e 3 1 3 nu 3 2 3
Adauga asta inainte de afisare:

Buna!

Imi da "Incorrect!" la testul al treilea, desi diff-ul cu ok-ul imi da ca e in regula. Stiti ce as putea face?

Multumesc!

Salut,

Problema e long-ul. https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models

Tu probabil ești pe 64 de biți, iar la tine long-ul e suficient pentru valoarea de infinit pe care ai ales-o, la noi nu este. De fapt e o coincidență destul de amuzantă că iei 95 de puncte: Fiindcă infinitul tău e putere a lui 2 valoarea devine exact 0 după overflow, deci ratezi doar cazurile în care răspunsul e negativ. Aparent doar testul 3 se ocupă de chestia asta. Poți testa pe http://ideone.com/ ce se întâmplă în sursa ta pe o platformă în care long-ul e pe 32 de biți.

Cred ca ar trebui modificate testele la problema asta. Eu iau 100 cu solutia asta, dar afisez gresit pe anumite teste: http://www.infoarena.ro/job_detail/1179543?action=view-source
exemplu test:
5
-1 5 -1 1 1
am vazut ca sunt mai multe surse de 100 care afiseaza 5 1 5 in loc de 6 2 5

Ar trebui micsorata limita de timp. Se poate obtine 100p in NlogN.

Aceasta sursa este luata de altundeva, am mai vazut chiar acelasi cod