1101 Raliu

[•andrei.12]

Aici puteți discuta despre problema Raliu.

[•vladtarniceru]

eu iau MLE cu un deque de int si un vector long long de 2.000.000
chiar nu am idei ce sa mai scot.. ma poate ajuta cineva?
multumesc

[•eudanip]

Nu stiu exact cum faci tu cu deque dar poti sa faci cu subsecventa de suma maxima (asa am facut eu). In felul acesta ai scapat de vectorul de tipul long long inlocuind-o cu o singura valoare de tipul long long (suma care o tii la fiecare pas).

Mult noroc.

[•vladtarniceru]

nu prea inteleg cum sa fac asta, eu in deque tin pozitiile in vectorul s (cel long long), iar la s am s[ i] = (b[1]-d[1]) + (b[2]-d[2]) + ... + (b[ i]-d[ i]) unde b[] sunt litri la o benzinarie si d[] distanta, deci nu prea vad cum cu o variabila  

[•skull]

Nu ai nevoie de long long decat pentru calculul sumei. Vectorul s e ok daca e int.

[•vladtarniceru]

daca pun s pe int iau incorect pe 4 teste, ca zice la restrictii ca e recomandat sa lucrezi cu var de tip long long (64 biti)

[•skull]

Numarul de litri de benzina si distanta nu-ti ies din int, la fel si diferenta dintre acestea. E ceva gresit in algoritmul tau. Incearca sa folosesti subsecventa de suma maxim, cum zicea si Daniel.

[•PlayLikeNeverB4]

Nici nu iti trebuie Deque neaparat. Poti retine pozitia p in care incepe subsecventa si daca depasesti p+n, scazi din suma elementul de pe pozitia p.

[•eudanip]

nu prea inteleg cum sa fac asta, eu in deque tin pozitiile in vectorul s (cel long long), iar la s am s[ i] = (b[1]-d[1]) + (b[2]-d[2]) + ... + (b[ i]-d[ i]) unde b[] sunt litri la o benzinarie si d[] distanta, deci nu prea vad cum cu o variabila 

http://infoarena.ro/algoritmiada-2011/runda-2/solutii

Solutia oficiala este cu subsecventa de suma maxima. Poate o intelegi de aici.

[•SebiSebi]

Va rog sa imi spuneti si mie un test mai mare. Nu inteleg de ce imi da incorect. Multumesc anticipat!

[•S7012MY]

S-ar putea mari putin limita de timp. Unele surse cum ar fi http://infoarena.ro/job_detail/671706 ar putea lua 100.

[•gabipurcaru]

Typo: "Traseu este circular, deci după benzinăria N urmeaza benzinăria 1" (lipseste un "l" din "Traseul")

[•gabipurcaru]

Cred ca problema asta trebuie imbunatatita, pentru ca un greedy optimizat a luat 100 destul de usor (http://infoarena.ro/job_detail/675768). In plus, nu exista niciun test care sa aiba (suma cantitatilor de benzina - suma distantelor) pozitiva, si totusi sa nu aiba solutie.

Si o mica intrebare: cum se face ca daca citesc doar cantitatile de benzina (http://infoarena.ro/job_detail/675766 -- evident, ia 0 puncte) face 292ms pe ultimul test, iar daca citesc si cantitatile de benzina si distantele (http://infoarena.ro/job_detail/675767) face 1436 ms? Codul relevant arata cam asa:

Cod:

for(i=1; i<=n; i++) {
	in>>b[i];
}
for(i=1; i<=n; i++) {
	in>>c[i];
}

Primul job are "in>>c[ i]" comentat, si cel de-al doilea nu.

[•alexalbu95]

Eu ce gresesc in rezolvarea mea? Am facut un ssm. http://infoarena.ro/job_detail/718368

[•Steve]

Eu ce gresesc in rezolvarea mea? Am facut un ssm. http://infoarena.ro/job_detail/718368

Um...nu prea avem cum sa stim ce ai tu prin cod, vad ca ai si TLE. Incearca sa faci problema pe hartie cu niste exemple, si o sa observi ceva (se poate afla pozitia de inceput in O(N) pur, daca exista vreo posibilitate de a parcurge traseul).

[•laurion]

foloseste long long

[•S7012MY]

Eu ce gresesc in rezolvarea mea? Am facut un ssm. http://infoarena.ro/job_detail/718368

Nu intra in timp decat cu stream-uri.

[•alexalbu95]

foloseste long long

Am folosit long long.

Eu ce gresesc in rezolvarea mea? Am facut un ssm. http://infoarena.ro/job_detail/718368

Um...nu prea avem cum sa stim ce ai tu prin cod, vad ca ai si TLE. Incearca sa faci problema pe hartie cu niste exemple, si o sa observi ceva (se poate afla pozitia de inceput in O(N) pur, daca exista vreo posibilitate de a parcurge traseul).

Am facut asta de 100 de ori pe hartie. Am vreo 80 de surse trimise numai la prob asta si tot 60pct iau. La una din ele aveam 4 incorecte si toate intrau in timp.

[•SpiderMan]

NU ai folosit long long pentru rezultat, vectorul a si N le lasi int, si schimbi doar REZULTATUL, adica x-ul ala din print (asa era parca), il faci long long, si afisezi cu "%lld".

[•alexalbu95]

NU ai folosit long long pentru rezultat, vectorul a si N le lasi int, si schimbi doar REZULTATUL, adica x-ul ala din print (asa era parca), il faci long long, si afisezi cu "%lld".

Ms. Acum am luat 100 pct.

[•SpiderMan]

TLE inseamna ca ai depasit limita admisa pentru problema, adica trebuie sa faci alt algoritm / sa optimizezi codul actual.

[•SebiSebi]

Incearca sa modularizezi si pune inline la functii , desi nu cred ca vei castiga mult timp.
Daca nu merge nici asa, poti parsa citirea http://infoarena.ro/parsarea-numerelor .

[•vladstoick]

@ Pirtoaca George Sebastian multumesc de idee ; 100 acum cu ajutorul parsarii ; Oricum cred ca timpul este prea mic pt ca am avut un coleg care si-a trimis din nou sursa de 100p si ia intre 70-90p acum

[•SebiSebi]

Da, normal ar fii sa iei 100 fara parsare. Poate o sa mareasca cineva limita de timp.

[•alexalbu95]

@ Pirtoaca George Sebastian multumesc de idee ; 100 acum cu ajutorul parsarii ; Oricum cred ca timpul este prea mic pt ca am avut un coleg care si-a trimis din nou sursa de 100p si ia intre 70-90p acum

Nu e nevoie de parsare. Eu doar am citit numerele normal cu streamuri. Poti lua 100 pct foarte usor.

Uite un raspuns pe care l-am primit eu la aceasta problema:

Se poate afla pozitia de inceput in O(N) pur, daca exista vreo posibilitate de a parcurge traseul.