|
Titlul: 954 Tester Scris de: Stefan Istrate din Noiembrie 23, 2009, 19:40:07 Aici puteti discuta despre problema Tester (http://infoarena.ro/problema/tester).
Titlul: Răspuns: 954 Tester Scris de: Savin Tiberiu din Noiembrie 23, 2009, 19:43:24 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?
Titlul: Răspuns: 954 Tester Scris de: Gheorghe Cosmin din Noiembrie 23, 2009, 21:22:43 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.
Titlul: Răspuns: 954 Tester Scris de: Pirtoaca George Sebastian din August 10, 2012, 16:21:12 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. Titlul: Răspuns: 954 Tester Scris de: Tudor Varan din Iulie 22, 2013, 09:23:45 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. Titlul: Răspuns: 954 Tester Scris de: Alexandru Valeanu din August 12, 2013, 10:01:29 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?
Titlul: Răspuns: 954 Tester Scris de: Geman Dorin Andrei din Aprilie 13, 2016, 17:50:08 1-2-3-5-4-R-2-4 Nu este solutie pentru primul exemplu?
|