035 Subsecventa de suma maxima

[•pauldb]

Aici puteti discuta despre problema Subsecventa de suma maxima din Arhiva educationala.

[•Florian]

E cam ciudat ca sursa asta ia TLE pe testul 19. Rezolvarea e O(N) ca timp si O(1) ca memorie. E din cauza citirii ? 

[•Marius]

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.

[•Mishu91]

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

Streamurile nu erau mai incete? 

[•Marius]

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

Streamurile nu erau mai incete? 

Acum sunt mai rapide.

[•Mishu91]

Ciudat... cu streamuri iau 70

[•Marius]

Ciudat... cu streamuri iau 70

Iar eu iau 100 așa.

[•Mishu91]

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

[•Florian]

Florian, iată: 100 cu sursa ta și 2s maxim pe test.

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

[•Marius]

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

Așa se pare.

[•stocarul]

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.

[•MciprianM]

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);

[•Marius]

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.

[•cvicentiu]

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.

[•Marius]

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.

[•cvicentiu]

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

[•wefgef]

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

[•c_e_manu]

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?

[•wefgef]

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

[•c_e_manu]

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

[•devilkind]

@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.

[•Marius]

@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.

[•pauldb]

@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.

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.

[•Addy.]

cu aceeasi sursa, si anume asta am luat pe rand 80, 90, 95, etc.
LE: nvm, am reusit.

[•Marius]

cu aceeasi sursa, si anume asta am luat pe rand 80, 90, 95, etc.
LE: nvm, am reusit.

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