Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: 1101 Raliu  (Citit de 4735 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
andrei.12
Echipa infoarena
Nu mai tace
*****

Karma: 107
Deconectat Deconectat

Mesaje: 381



Vezi Profilul
« : Februarie 20, 2011, 20:32:33 »

Aici puteți discuta despre problema Raliu.
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #1 : Martie 04, 2011, 18:41:58 »

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
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #2 : Martie 04, 2011, 19:41:23 »

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.
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #3 : Martie 05, 2011, 09:20:31 »

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  Huh

Memorat
skull
Client obisnuit
**

Karma: 17
Deconectat Deconectat

Mesaje: 75



Vezi Profilul
« Răspunde #4 : Martie 05, 2011, 09:34:57 »

Nu ai nevoie de long long decat pentru calculul sumei. Vectorul s e ok daca e int.
« Ultima modificare: Martie 05, 2011, 10:17:35 de către Lepadat Mihai-Alexandru » Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #5 : Martie 05, 2011, 16:28:55 »

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)
Memorat
skull
Client obisnuit
**

Karma: 17
Deconectat Deconectat

Mesaje: 75



Vezi Profilul
« Răspunde #6 : Martie 05, 2011, 17:16:36 »

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.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #7 : Martie 05, 2011, 17:34:46 »

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.
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #8 : Martie 06, 2011, 13:26:24 »

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  Huh


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

Solutia oficiala este cu subsecventa de suma maxima. Poate o intelegi de aici.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #9 : Noiembrie 11, 2011, 16:08:36 »

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

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #10 : Ianuarie 31, 2012, 19:34:12 »

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


Karma: 13
Deconectat Deconectat

Mesaje: 24



Vezi Profilul
« Răspunde #11 : Februarie 08, 2012, 08:11:50 »

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


Karma: 13
Deconectat Deconectat

Mesaje: 24



Vezi Profilul
« Răspunde #12 : Februarie 08, 2012, 09:21:45 »

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.
« Ultima modificare: Februarie 09, 2012, 08:56:24 de către Gabi Purcaru » Memorat
alexalbu95
Client obisnuit
**

Karma: -10
Deconectat Deconectat

Mesaje: 57



Vezi Profilul
« Răspunde #13 : Martie 20, 2012, 18:48:58 »

Eu ce gresesc in rezolvarea mea? Am facut un ssm. http://infoarena.ro/job_detail/718368
Memorat
Steve
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #14 : Martie 20, 2012, 22:18:33 »

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).
Memorat
laurion
De-al casei
***

Karma: -41
Deconectat Deconectat

Mesaje: 102



Vezi Profilul
« Răspunde #15 : Martie 20, 2012, 22:52:53 »

foloseste long long
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #16 : Martie 20, 2012, 22:57:12 »

Eu ce gresesc in rezolvarea mea? Am facut un ssm. http://infoarena.ro/job_detail/718368
Nu intra in timp decat cu stream-uri.
Memorat
alexalbu95
Client obisnuit
**

Karma: -10
Deconectat Deconectat

Mesaje: 57



Vezi Profilul
« Răspunde #17 : Martie 21, 2012, 14:12:42 »

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.
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #18 : Martie 21, 2012, 14:28:19 »

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".
Memorat
alexalbu95
Client obisnuit
**

Karma: -10
Deconectat Deconectat

Mesaje: 57



Vezi Profilul
« Răspunde #19 : Martie 25, 2012, 17:54:57 »

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. Very Happy Acum am luat 100 pct.
« Ultima modificare: Aprilie 06, 2012, 11:12:59 de către Albu Alexandru » Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #20 : Aprilie 13, 2012, 10:09:51 »

TLE inseamna ca ai depasit limita admisa pentru problema, adica trebuie sa faci alt algoritm / sa optimizezi codul actual.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #21 : Aprilie 13, 2012, 10:29:13 »

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 .
Memorat
vladstoick
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #22 : Aprilie 15, 2012, 09:59:24 »

@ 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
« Ultima modificare: Aprilie 15, 2012, 10:06:20 de către Stoica Vlad » Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #23 : Aprilie 15, 2012, 11:07:33 »

Da, normal ar fii sa iei 100 fara parsare. Poate o sa mareasca cineva limita de timp.
Memorat
alexalbu95
Client obisnuit
**

Karma: -10
Deconectat Deconectat

Mesaje: 57



Vezi Profilul
« Răspunde #24 : Aprilie 16, 2012, 10:16:40 »

@ 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.
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines