209 Sir

[•fireatmyself]

Aici puteţi discuta despre problema Sir.

[•filipb]

A reusit cineva sa scoata O(N)?

[•wefgef]

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

[•alexthero]

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:

-    Valorile sirului sunt numere naturale ≤ 30.000

[•coldfirero]

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.

[•Marius]

Si eu am scos O(N)...   

[•tm_radu]

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

[u-92]

o cautare binara te poate ajuta

[•Marius]

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. 

[•tm_radu]

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?

[•Marius]

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

[•tm_radu]

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];
}

? 

[•Marius]

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

[•tm_radu]

A da ...am inteles  ...sorry....

[•ion824]

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

[•andrei.arnautu]

Este ceva special la testul 14? E singurul care imi pica, iau 95p.

[•TrascaAndrei]

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.

[•Al3ks1002]

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.

[•Daria09]

Imi da WA pe testele 2 si 4  .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 ? (p.s. n-am folosit cautarea binara cum spune in indicatii)

[•usureluflorian]

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?