UVA Contest of Newbies 2007

[•domino]

Sambata, 29 decembrie, ora 14:00, va avea loc concursul Contest for Newbies 2007 pe site-ul UVA Online Judge.

[•cos_min]

A facut careva D sau E, sa explice putin cum si ce au facut. Sau unde as putea gasi solutiile oficiale ?

[•filipb]

Eu nu am participat, dar am citit problemele A si E. E nu mi s-a parut asa de grea, cel putin la prima vedere. Ma gandisem la o dinamica: M(i) = cate numere poti forma cu exact i bete de chibrit. Acum tu incerci sa adaugi cifrele de la 0 la 9. Sa zicem ca cifra x este formata din bete(x) bete de chibrit. Ai relatia de recurenta:
M(i) = suma(M(i-bete(x))), x de la 0 la 9.
Rezultatul va fi in M(1) + M(2) + ... + M(N).

Am citit acum si D.
Complexitate: O(N^2). Cel mai simplu mi se pare asa: faci un nou graf cu noduri de forma: (x nr), cu semnificatia ca te afli in graful initial in nodul x si ai ajuns aici folosind de nr ori Commercial Express. Evident, nr poate fi 0 sau 1 ( nu poti folosi tipul ala special decat cel mult o data ), deci ai exact 2N noduri in noul tau graf. Muchiile in graful nou: pui muchie de la (x 0) la (y 0) si de la (x 1) la (y 1) egala cu costul muchiei de la x la y pentru Economy-Xpress. De la (x 0) la (y 1) pui muchia de cost egal cu costul dintre x si y in Commercial-Xpress. Numarul tau de muchii va fi deci 2M + K.
Acum faci un Djikstra de sursa (S 0). Afisezi minimul pentru destinatia (E 0) ( caz in care nu folosesti biletul ala ) sau destinatia (E 1) ( caz in care il folosesti ).

Nu m-am gandit foarte mult la ele, sper ca nu m-am grabit cu explicatiile .

[•pauldb]

Pentru D:

Calculezi c[ i ] = costul minim de la sursa la nodul i doar cu primele muchii si d[ i ] = costul minim de la destinatie la nodul i doar cu primele muchii. Apoi rezultatul va fi in min(c[destinatie], c[x[ i ]] + d[y[ i ]] + z[ i ], c[y[ i ]] + d[x[ i ]] + z[ i ]), unde x[ i ], y[ i ] z[ i ] sunt caracteristicile unei muchii de tipul 2.

[•cos_min]

Merci pentru explicatii.
La E am facut ceva de genu : A(i)(k)(j) - numarul de nr formate din i cifre care dau suma j, folosind ult cifra k. Se pare ca m-am complicat prea mult si am luat TLE.

La D am facut: D(i)(0) - costul minim daca pana in i daca nu am folosit inca o muchie din cele K D(i)(1) - costul minim daca pana in i daca am folosit deja muchie din cele K. Si aici am luat TLE, avand o compl prea mare, O(n^3).

[•cos_min]

S-au pus cumva pb in arhiva lor ?

LE. Le-am gasit.