954 Tester

[•stef2n]

Aici puteti discuta despre problema Tester.

[•devilkind]

Am si eu o intrebare in legatura cu solutia oficiala. Graful initial are 5000 de muchii ceea ce inseamna ca graful care rezulta avea 5000 de noduri si aproximativ 5000^2 muchii (aici e posibil sa ma insel dar oricum mi se pare ca numarul de muchii poate fi foarte mare) ceea ce inseamna ca nu prea aveai cum sa tii acest graf in memorie. Voi ati tinut graful pur si simplu sau numai l-ati simulat tinand numai graful initial?

[•gcosmin]

Limita superioara pentru numarul de muchii din graful rezultat este N * M, nu M^2 cum ai aproximat tu. Fiecare muchie (x, y) poate avea maxim N muchii care intra capatul in x si maxim N muchii care ies din y. De aici putem deduce ca in graful rezultat fiecare nod (adica muchie din graful initial) are cel mult 2 * N vecini (N intra, N ies) => cel mult N * M muchii in total => si complexitatea de N * M a solutiei.

[•SebiSebi]

Se mai poate lua 100 de puncte? Eu folosesc algoritmul pentru ciclu eulerian , iterativ, identic cu cel care ia 100 in arhiva educatonala si am TLE pe testul 8. Am implementat liste simplu inlantuite manual si TLE - ul ramane.

Am luat pana la urma 100 de puncte inlocuind doar listele care nu erau necesare cu vectori alocati static.

[•tudorv96]

Pentru exemplul al doilea 1 2 3 2 3 1 4 3 4 nu este un raspuns valid? Fiecare combo posibil are o singura aparitie, iar numarul de resetari este minim.

LE: Nu apare fiecare combo posibil(lipseste 1 4 3 2 spre exemplu), doar secventa de taste apare fara sa fie necesara resetarea.

[•AlexandruValeanu]

Am si eu o intrebare legata de muchiile din graful in care se cauta ciclul: muchie este i->j cu i si j citite din fisiere sau i->k cu i->j si j->k cele 2 taste din fisier?

[•dorin31]

1-2-3-5-4-R-2-4 Nu este solutie pentru primul exemplu?