Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 209 Sir  (Citit de 5680 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
fireatmyself
Nu mai tace
*****

Karma: 36
Deconectat Deconectat

Mesaje: 492



Vezi Profilul
« : Martie 29, 2006, 18:05:04 »

Aici puteţi discuta despre problema Sir.
Memorat

Viata e scurta. Daca nu o putem lungi, macar s-o facem lata.
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #1 : Martie 29, 2006, 20:04:53 »

A reusit cineva sa scoata O(N)?
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #2 : Martie 29, 2006, 20:20:59 »

ma mai chinui putin. iau WA pe 3 teste si nu stiu de ce Brick wall  Brick wall  Brick wall
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
alexthero
De-al casei
***

Karma: 121
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #3 : Aprilie 07, 2006, 11:54:09 »

Am o rezolvare care ia 90-95 de puncte. Iau WA pe testul nr 14. Am trimis o rezolvare care verifica si datele de intrare si cred ca acest test nu corespunde la conditia:
Citat
-    Valorile sirului sunt numere naturale ≤ 30.000
Memorat

Tine minte ca mintea conduce pumnu, nu invers
coldfirero
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #4 : Aprilie 07, 2006, 13:08:21 »

Da ai dreptate, am verifcat testul respectiv si exista ~ 5-6 valori de 30001 si 30002 ...
Cred totusi ca o poti rezolva si in acest caz .. nu vad un impediment.
Probabil ca enuntul va fi modificat.
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #5 : Iunie 26, 2006, 20:25:01 »

Si eu am scos O(N)...   Very Happy
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #6 : Iunie 26, 2006, 21:05:57 »

Imi zice si mie cineva o idee cam cum ar trebui rezolvata problema?
Memorat

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
u-92
Vizitator
« Răspunde #7 : Iunie 28, 2006, 22:32:05 »

o cautare binara te poate ajuta
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #8 : Iulie 02, 2006, 03:16:41 »

Ideea de O(N) pe care am avut-o a fost sa stiu la fiecare pas unde incepe secventa si sa tot aleg o pozitie convenabila doar avansand, normal. Acum nu iti mai ramane decat sa stii ce valori ai in intervalul tau.  Tongue
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #9 : Iulie 02, 2006, 17:42:13 »

Presupunand ca am un sir a[] de n elemente, si un subsir de lungime l, al carui inceput il iau pe rand pe ppozitiile 1, 2, ....n-l, care este cea mai eficienta metoda pentru a stii minimul si maximul din subsecventa de lungime l?
Este vreo metoda sau trebe sa verific pentur fiecare pozitie de inceput in O(l) minimul si maximul?
Memorat

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #10 : Iulie 02, 2006, 17:58:09 »

Presupunand ca am un sir a[] de n elemente, si un subsir de lungime l, al carui inceput il iau pe rand pe ppozitiile 1, 2, ....n-l, care este cea mai eficienta metoda pentru a stii minimul si maximul din subsecventa de lungime l?
Este vreo metoda sau trebe sa verific pentur fiecare pozitie de inceput in O(l) minimul si maximul?

Minimul si maximul il construiesti treptat pe masura ce avansezi cu pozitiile tale cu ajutorul a doua deque-uri. Uite:
Cod:
pentru k = 1, N executa
     pui in deque-uri A[k]
     cat timp (prima pozitie este mai departata de Y pozitii de k sau Maxim - Minim > Z) si nu esti mai aproape de X pozitii de k executa
           ++first
           elimini elementele din cele doua deque-uri care nu sunt in intervalul [first, k]
     vezi si tu...

Intuitiv mi se pare bine...
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #11 : Iulie 02, 2006, 18:10:09 »

Nu cred ca ai inteles ce am intrebat de fapt. Am doua variabile maxim si minim.
Cum stiu in timpul rularii, care este maxim si care este minim, pentru un anume i (1...n-l) si care este cea mai eficienta metoda sa le determin, ca sa nu fac :

Cod:
for ( i = 1; i <= n-l; i++ )
{
    minim = 32000, maxim = -32000;
    for ( j = i; j <= i + l; j++ )
         actualizez maxim si minim, in functie de fiecare a[j];
}

Think
Memorat

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #12 : Iulie 02, 2006, 18:30:01 »

Eu cred ca tu nu m-ai inteles... prima valoare din deque este minimul/maximul cautat.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
tm_radu
De-al casei
***

Karma: 16
Deconectat Deconectat

Mesaje: 140



Vezi Profilul
« Răspunde #13 : Iulie 02, 2006, 22:20:30 »

A da ...am inteles  Aha...sorry....
Memorat

Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
ion824
Strain


Karma: 11
Deconectat Deconectat

Mesaje: 17



Vezi Profilul
« Răspunde #14 : Iulie 12, 2011, 20:04:19 »

Imi poate sugera cineva de ce imi pica al 2-lea test...in rest toate merg perfect, am 95 puncte si nu-mi pot gasi greseala in program...
Memorat
andrei.arnautu
Client obisnuit
**

Karma: 9
Deconectat Deconectat

Mesaje: 58



Vezi Profilul
« Răspunde #15 : Ianuarie 06, 2015, 01:47:13 »

Este ceva special la testul 14? E singurul care imi pica, iau 95p. Brick wall
Memorat
TrascaAndrei
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 18



Vezi Profilul
« Răspunde #16 : Martie 07, 2016, 21:46:15 »

Am si eu o intrebare. Functiile consuma mult timp? Adica m-am chinuit o gramada sa iau 100 de puncte la problema asta, chiar daca o faceam in O(N). Am incercat pana si parsarea si m-a ajutat sa ajung de la 80 la 90, tot am avut 2 teste cu TLE. Apoi m-am gandit sa scot o functie si am ajuns de la peste 0,3 secunde la 8ms. Nu prea inteleg de ce.
Memorat
Al3ks1002
Strain


Karma: 5
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #17 : Martie 07, 2016, 22:06:57 »

Asta e pentru ca tu transmiti prin valoare un obiect de tip deque de fiecare data cand apelezi functia. Practic copiezi tot deque-ul care il ai intr-un nou deque de fiecare data cand apelezi. Incearca sa transmiti doar adresa (adica prin referinta) si ai sa vezi ca o sa mearga rapid.
Memorat
Daria09
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #18 : Martie 08, 2016, 16:47:50 »

Imi da WA pe testele 2 si 4  Brick wall.Am facut problema in o(n) cu doua cozi(una pentru minim,alta pentru maxim).Imi puteti da niste teste sau o idee pentru 100 ? Smile (p.s. n-am folosit cautarea binara cum spune in indicatii)
Memorat
usureluflorian
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #19 : Martie 08, 2017, 21:29:47 »

Eu iau 95 puncte, sursa mea pica pe testul 2 WA. I s-a mai intamplat cuiva asta si a gasit ce e cu testul acela?
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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