361 Johnie

[•danielp]

Aici puteţi discuta despre problema Johnie.

[•stef2n]

La campion am luat 80 de pct pe problema aceeasta, cu "Killed by signal: 11" pe ultimele 2 teste (probabil din cauza unui DF recursiv). Pe infoarena2 am trimis aceeasi sursa si am luat 100 de pct. Limitele de memorie sunt aceleasi? Adica 16 MB din care 1 MB pentru stiva?

[•danielp]

Sigur faci recursiv. La campion stiva era doar de 1 MB, acolo ti-a iesit din stiva. Aici nu cred ca e limitata stiva, si nu a mai iesit .

[•tvlad]

E cam stransa limita de timp, daca era 0.5 intra recursiv, asa trebuie facuta iterativ.

[•pauldb]

Cred ca asta intentiona si autorul. In concurs a fost la fel.

[•unknownliviu]

Am si eu o problema. Eu calculez intr-un for traseele pentru fiecare etapa , deci nu stiu decat dupa ce le-am calculat pe toate care este numarul de etape, iar problema imi cere sa afisez pe primul rand numarul de etape. Banuiesc ca salvarea traseelor este ineficienta    Sugestii?

[•wefgef]

Numarul de noduri cu grad impar / 2?

[•vendetta]

o idee despre rezolvarea mea i`au 0 pct cu mesaj "drum invalid"; : am facut pt fiecare nod un ciclu/lant eulerian;si apoi afisez lanturile cu dimensiunea mai mare de 1;

[•stocarul]

Am şi eu o mică nelămurire.
Numărul de trasee nu ar trebui să fie nrNodGradImpar / 2 + numărComponenteConexeFărăNoduriCuGradImpar?
Asta deoarece pot avea o componentă conexă fără noduri de grad impar ... şi pot forma un ciclu eulerian acolo.

Totuşi, dacă fac aşa ... primesc număr lanţuri incorect pe câteva teste ....

[•SebiSebi]

Cam stransa limita de timp. Cu Hierholzer iau TLE pe 4 teste. Am renuntat la cautarea secventiala din stergere folosind hashing dar merge mai lent iar parsarea scade din timp , dar nu suficient. Complexitatea algoritmului este O(m). Ce as mai putea optimiza? Multumesc anticipat!

[•Dddarius95]

sall.cat va da pe testele urmatoare?

Cod:

15 15
1 2
2 3
3 4
4 5
5 3
3 6
6 7
7 8
8 9
10 11
11 12
12 10
11 14
14 15
15 11

Cod:

16 15
1 2
2 3
3 4
4 5
5 3
3 6
6 7
7 8
8 9
10 11
11 12
12 10
11 14
14 15
15 11

mie imi da asa

Cod:

2
10 9 8 7 6 3 5 4 3 2 1 
7 10 12 11 15 14 11 10 

Cod:

2
10 9 8 7 6 3 5 4 3 2 1 
7 10 12 11 15 14 11 10 

[•danalex97]

Cu sursa de 100 imi da:

Cod:

1
10 9 8 7 6 3 5 4 3 2 1

Cod:

1
10 9 8 7 6 3 5 4 3 2 1

[•andreiulian]

Am o nelamirire, nodurile sunt numerotate de la 1 la N sau poate exista un nod 0 ?

[•SebiSebi]

De obicei, dacă nu se precizează în enunț altfel, nodurile unui graf sunt numerotate începând cu 1.

[•andreiag]

Poate sa-mi explice cineva de ce in testul acesta (de-a lui Dddarius95)

Cod:

15 15
1 2
2 3
3 4
4 5
5 3
3 6
6 7
7 8
8 9
10 11
11 12
12 10
11 14
14 15
15 11

se obtine:

Cod:

1
10 9 8 7 6 3 5 4 3 2 1

Graful acesta are 2 componente conexe, deci ar trebui sa fie 2 etape in solutie, nu?