infoarena

Aici puteti discuta despre problema NumMst (http://infoarena.ro/problema/nummst).

Imi poate explica si mie cineva de ce este necesar ca n sa fie compus?
Daca avem n = 7 nu ar fi raspunsul 3 4?

@Marginean Ciprian:
Complexitatea solutiei oficiala se bazeaza pe o teorema care e valabila numai in cazul numerelor compuse. Pentru numere prime complexitatea ar fi prea mare.

Pentru n prim, putem face doua observatii:

1) Cmmdc-ul numerelor ce dau suma n va fi 1.

Dem.: Fie v1, v2..vk, astfel incat v1+v2+..+vk = n

Cmmdc(v1, v2..vk) divide n, dar n este prim, rezulta cmmdc = 1. (daca cmmdc = n rezulta k = 1 contradictie).



Acum, considerand cazul n compus, putem face urmatoarea observatie:

v1 = cmmdc * x1, v2 = cmmdc * x2 .. vk = cmmdc * xk

Noi vrem sa calculam cmmmc (v1, v2, .. vk).

Cmmmc(v1, v2 .. vk) = cmmdc(v1, v2..vk) * cmmmc(x1, x2 .. xk).

Stim ca suma x1 + x2 + ... + xk = S <= sqrt(n). (Alegem cmmdc-ul maxim => n / cmmdc <= sqrt(n)).

Problema se reduce la a gasi termenii x1, x2, .. xk astfel incat cmmmc(x1, x2, .. xk) sa fie maxim.

Acest lucru se poate rezolva cu o dinamica S * nr_prim, unde nr_prim reprezinta numarul de numere prime <= S.

2) Daca n ar fi prim, atunci x1 + x2 + .. + xk = v1 + v2 + .. + vk = n, deci solutia ar rula in O(n * nr_factori_primi <= n), ce ar depasi limita de timp, si ar forta o restrictie destul de stransa pentru n, gen 3000.

De aici vine restrictia n compus. Nu stiu daca exista un algoritm pur greedy pentru a genera cmmmc-ul maxim, si din ce stiu, toti cei care au luat 100 in concurs s-au bazat pe abordarea folosind programare dinamica.

Sper sa nu ma insel :).