infoarena

Aici se pot pune întrebări legate de problema Queue de la Runda 2 a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

Toate valorile folosite in operatiile de push vor fi numere intregi ≤ 10^6.
Sunt numai numere naturale sau pot fi si negative?

Daca pentru a face operatia 'x' am nevoie de mai mult de 500 k de caractere de afisat, pot afisa pe 2 linii?

x: ..
x: ..

Eu nu am inteles exact ce trebuie sa facem.Nu vad nici o cerinta. :?

Restrictia asta sigur e corecta?

In loc de ultimia linie din .out de la ex:"5: read(2) push(2,2)" putea fi si "5: read(2) push(1,2)"?

Se garanteaza ca exista cel putin un element in coada cand se face operatia pop_front() ?

Se garanteaza ca in operatiile sunt valide? ( Nu o sa se ceara scoaterea unui element cand stiva este goala )

sunt de acord cu geniucos ar trebui sa fie mai clara problema nu intaleg nimic din enunt.

@Mihai22e naturale
@veleandu NU
@geniucos Citeste mai atent, si restrictiile si inputul.
@gramatovici_paul DA
@andreii1 DA
@elfus2 & veleandu Operatiile sunt valide

Este obligatoriu ca operatiile din out sa se execute in ordinea 1, 2, ... N ?

No comment

Daca te referi daca afisarile sa se execute in ordinea 1..N, raspunsul este DA.

Ce ar trebui sa insemne feedback-ul "Variabila de push invalida"?

Ca faci push cu o valoare != wr.

Solutia este unica?

Se mai poate adauga un test la feedback?

@narcis_vs No comment, citeste raspunsurile de mai sus.

De ce este gresit output-ul acesta ?
1: read(3) push(1,3)
2: read(5) push(1,5)
3: pop(1) push(2,5) pop(1) push(2,3) pop(2) write(3)
4: pop(2) write(5)
5: read(2) push(1,2)
Nu inteleg . :|

ce inseamana:"Afisare invalida a valorii WR"?

nu e gresit, si sursa mea da exact acelasi output pe exemplu, si ia ok pe testul de feedback.
ai grija la restrictia "O operatie de push efectuata pe una dintre stive se considera valida daca valoare folosita se afla in WR."

Am folosit read(2) => Este folosita in WR, deci pot folosi push(1,2) ; Chiar nu inteleg !!!

Mi-am dat seama.

aici, tu il citesti pe 5 (wr = 5), apoi scoti varful din stiva 2 (wr = varful = 2), il introduci pe wr (=2) in prima stiva, dupa care incerci sa il introduci si pe 5 (numarul citit initial) in aceeasi stiva.
ultima operatie nu respecta restrictia scrisa mai sus, pentru ca functiei push() ii poti da ca parametru doar valoarea actuala a variabilei wr, iar tie ti se pierde acea valoare.

corect ar fi cam asa:

testul 1 e exemplul??

Intr-un worst case, sursa mea afiseaza peste 750.000 de caractere pe un rand. Totusi am luat 100.  Nu sunt singuru in situatia asta. Modificati testele sau modificati restrictia?

Cum pot sa afisez cat mai rapid instructiunile?
Daca afisez cu printf("text") iau tle.

LE: TLE-ul nu era de la afisare, ci de la algoritm. Am schimbat metoda de rezolvare si acum iau 100 puncte.

care este solutia optima?eu iau tot 30..si nu cred ca pop sa o mai optimizez...

Paul are dreptate ..
Adi craciun are o solutie destul de smechera, care merge cu limita aia cu 500k pe linie, dar personal, cred ca se freaca la timp :-s

Ca sa iti intre bine in limite, observai ca poti sa ai maxim 15000 pop_front()-uri. Deci nu aveai nevoie sa afisezi vreodata mai mult de primele 15000 elemente intrate, asa ca bagai in seama doar maxim primele 15000 de push_back()-uri (daca nu, puneai "read(...)", dar nu introduceai valoarea in stiva). Asa ti se injumatatea numarul de elemente din stiva, deci ti se injumatatea si dimensiunea maxima a unei linii.

Interesant ...
Eu aveam 2 stive, una in care puneam si alta din care scoteam.
Daca nu aveam ce scoate, scoteam tot din stiva de entry si puneam tot in cea de exit, si practic imi rasturnam stiva.

Ai dreptate Rares, dar daca am deja cateva elemente in stiva de exit, cum pot rasturna stiva de entry? :-s

Pai cred ca merge oricum, adica tu atunci cand inserezi un element nou intr-o stiva verifici daca nu cumva ai inserat in total mai mult de 15000.

Faci la fel ca in solutia ta.
Singura modificare e ca, atunci cand iti vine un query "push_back()", daca ai avut pana la acel moment deja 15000 de push_back()-uri il ignori (faci doar "read()"-ul, fara sa mai pui nicaieri elementul).

Glumesti?
Adica .. tu te folosesti de un glitch in evaluator .. in sensul ca in realitate nu ar merge asta.

+1.