Solutii la concursul acm 2013 etapa nationala partea a doua

[•Cosmin]

http://www.infoarena.ro/blog/acm-2013-etapa-nationala-partea-ii

[•MciprianM]

Salut!
La problema Power Calculus, de ce ajunge sa expandam doar nodurile care au distanta minima pana la ele egala cu distanta minima pana la ultimul numar generat?

De exemplu:
1 2 3
1 2 4
sunt noduri care se genereaza, dar
1 2 3 4
nu se genereaza, pentru ca are costul trei, iar ultimul numar generat(4) poate fi obtinut cu cost 2.

Adica, nu e posibil sa existe vreun nod de genul 1 2 3 4 din care sa se obtina cu cost minim alt numar? In cazul asta 7 ar fi numarul, dar 7 se obtine de exemplu din 1 2 3 6, care e e un nod generat, deci pentru 7 e ok. Cum demonstram ca e ok pt toate numerele?

Mersi.

[•PlayLikeNeverB4]

Daca ai avea nevoie de acel 3 atunci ti l-ai putea crea cand ai nevoie de el. In exemplul tau, din 1 2 4 poti face 1 2 4 (...) 7 in doua mutari (aduni 1 si 2 la 4). Practic l-ai adaugat pe acel 3 folosind si mutarea pe care nu ai folosit-o ca sa il creezi efectiv pe 3.
Nu stiu sa demonstrez formal ca e corect.

[•MciprianM]

Tu zici ca dacă ai avea nevoie de 3 ți l-ai putea crea. În algoritmul asta nu poți.  Deci ar trebui sa arăți ca nu ai nevoie...
În cazul 7 soluțiile considerate sunt
1 2 3 6 7
1 2 3 5 7
1 2 4 6 7
1 2 4 8 7

[•PlayLikeNeverB4]

Eu am zis ca in loc sa il creezi explicit, il "creezi" prin faptul ca aplici aceleasi operatii asupra ultimului element.