infoarena

Runda 8 (http://infoarena.ro/monthly-2012/runda-8) a concursului Monthly 2012 (http://infoarena.ro/monthly-2012) s-a încheiat. Felicitări primilor clasați (http://infoarena.ro/monthly-2012/runda-8/clasament)!

Premiul special oferit de catre firma IXIA (http://www.ixiacom.com) va merge la Olariu Ciprian (http://infoarena.ro/utilizator/scipianus), deoarece a rezolvat problema Triangles avand penalizarea (19 puncte) cea mai mica dintre cei inscrisi in concurs! Felicitari!

Asteptam opiniile si eventualele sugestii ale voastre în legatura cu organizarea, subiectele propuse și orice probleme intampinate.

Mult succes în continuare!

Interesanta runda... a fost una reusita... Imi puteti spune cum se facea cifre? Am incercat cu numere prime mai mici ca 10, sa fac toate combinatiile posibile, dar nu prea am reusit sa scot mare branza.

Frumoasa runda :ok:.Cand o sa se introduca problemele in arhiva Monthly?

Felicitari pentru runda. Au fost probleme foarte bine calibrate pe dificultate. Se poate updata si ratingul ?

@Mihai Visuian. O sa incerc eu sa-ti explic.  :-' Cine vrea sa se mai gandeasca, il sfatuiesc sa sara peste postul asta.

Incep cu un caz mai special: intervalul [1, 10^B - 1]. Te intereseaza toate numerele diferite x care se pot scrie ca produs de cel mult B cifre. Fiecare numar x va avea o descompunere in factori primi. Asadar, te intereseaza toate descompunerile in factori primi diferite. Observi ca singurii factori primi care pot aparea in descompuneri sunt 2, 3, 5 si 7. Cea mai mare descompunere ipotetica ar fi 2^60 * 3^40 * 5 ^ 20 * 7 ^ 20 (daca ai folosi de B ori cifrele 8, 9, 5 si 7). Deci sunt maxim 60 * 40 * 20^2 posibilitati = 960000 de descompuneri, care pot fi iterate. Mai ramane de rezolvat o problema: avand o descompunere 2^a * 3^b * 5^c * 7^d, se poate obtine ca produs de cel mult B cifre? Pentru factorii 5 si 7, trebuie folosite c + d cifre (c cifre de 5 si d cifre de 7). Acum, pentru puterile lui 2, este optim ca folosind o singura cifra de 8 sa reduc a-ul cu 3. Dupa ce nu se mai poate scadea 3 din a (a < 3), am 3 posibilitati:

1. folosesc o cifra de 6 si obtin un a si un b mai putin in descompunere
2. folosesc o cifra de 4 si obtin si obtin 2 de a mai putin in descompunere
3. folosesc o cifra de 2 si obtin un a mai putin de descompunere

Aceeasi situatie se intampla si pentru 3. Folosind greedy, este optim sa iau cat mai mult posibil. Intai o sa aplic 2. pe numerele a si b. Daca atat a cat si b ajung 1, le aplic 1. (folosind o cifra de 6, in loc de una de 2 si una de 3) Altfel, folosind o 3. o sa iau cifra. Acum am numarul de cifre minim (adunand toate numerele de mai sus) pentru care se poate obtine descompunerea 2^a * 3^b * 5^c * 7^d. Daca este <= B, atunci descompunerea e valida.

Mai ramane problema pe caz general [10^A, 10^B - 1]. Aceasta poate fi redusa usor la problema de mai sus. Daca pt o descompunere, numarul minim de cifre este < A, se mai pot adauga 1 care nu vor influenta rezultatul pana se vor obtine A cifre.

Descompunerile in factori primi ajuta pentru numere >= 2, dar mai raman numerele 0 si 1. Numarul 0 se poate obtine de fiecare data cand B > 1 (spre exemplu, numarul 10 va genera valoarea 0). Numarul 1 se poate obtine pt orice valoare a lui A, deci la rezultat se va adauga 1 si se va obtine rezultatul final. Observi ca valoarea lui A nu influenteaza deloc problema.

Sper ca ti-am fost de ajutor. Mult succes. Mi-au placut problemele, mai ales ca au necesitat gandire, nu numai algoritmi. As vrea si eu un hint la Triangles. :) Am gasit o solutie O(N * logN), care nu intra in timp.

Multumesc :)

@elfus Gandeste-te daca ai nevoie de toate numerele.
@Costin Am adaugat acum problemele.

Frumoase problemele. Mi s-a parut un set potrivit. Felicitari.  =D&gt;
Am vazut ca la cifre era corecta si formula recurenta V[ i ]=V[i-1]+(v+1)*(v+1)*(v+1). Imi poate explica cineva de unde s-a dedus ?

i-ul ce reprezinta?

i reprezinta puterea lui B. Chestia e valabila de la 3 in sus inclusiv.

si rezultatul este v[ B  ]+v[A]  ?
v[0]=1?

Felicitari echipei si propunatorilor pentru problemele interesante  :D
P.S. : Are timp cineva sa updateze ratingurile(pentru rundele 7 si 8 )?  :)

Rezultatul e V[ B ].

@elfus : am completat eu solutia la Triangles (http://infoarena.ro/monthly-2012/runda-8/solutii (http://infoarena.ro/monthly-2012/runda-8/solutii))
Poate cineva sa completeze si la Culori4? :D

Pe viitor incearca sa completezi pe pagina problemei http://infoarena.ro/monthly-2012/runda-8/solutii/triangles

@Ciprian, nu cred ca am inteles metoda ta. Iti merge pt N = 4 K = 3 si sirul 8 2 2 2 sa dea 2 3 4 ? Adica din cate am inteles, faci asa

1) Bagi secventa {8, 2, 2} min-heapul e {2, 2, 8} si maximul e 8. 2 + 2 < 8 asa ca continui
2) Scoti 2 din min-heap, bagi urmatorul 2 si min-heapul arata tot {2, 2, 8} cu maximul 8. Din nou conditia nu e respectata. Mai departe ce faci?

Daca imi iese culori4 o sa incerc sa completez eu solutia :)

Good point #-o Chiar e un caz la care nu m-am gandit,deci solutia nu e pe deplin gandita bine  :-k

Ma gandesc ca in loc de heap, ai putea sa folosesti un multiset, care iti tine sortate elementele, si asa de fiecare data cand citesti un element vei avea 3 cazuri:

1) x>min: Scot minimul si il introduc pe x.
2) x<max: Scot maximul si il introduc pe x.
3) x<=min sau x>=max: nu fac nimic.

Asa merge si cazul {8,2,2,2}.

Yeah. O să facem un efort să scriem noi soluțiile de acum. Poate chiar sub formă de editorial. Doar așteptati puțin  :)

Edit: Done, avem blogpost.

Nu ar trebui marita limita de timp la problema triangles, mie in pascal numai citirea parsata intra in 188 ms si nu prea cred ca raspunsul 
la problema se poate afla in mai putin de 12 ms   ](*,) :?

De ce nu treci pe C++?

Am incercat si in CPP, dar am primit acelasi rezultat  ](*,)
http://infoarena.ro/job_detail/788657

Pai nu ai solutia buna :).

Citeste fara streamuri.
Edit: Aa, da. Si intr-adevar, citesti prea multe numere  :-'

Cand se va tine runda a 9-a?