|
Titlul: UVA Contest of Newbies 2007 Scris de: Mircea Pasoi din Decembrie 26, 2007, 20:16:18 Sambata, 29 decembrie, ora 14:00, va avea loc concursul Contest for Newbies 2007 (http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=12) pe site-ul UVA Online Judge (http://icpcres.ecs.baylor.edu/onlinejudge/index.php).
Titlul: Răspuns: UVA Contest of Newbies 2007 Scris de: Bondane Cosmin din Decembrie 30, 2007, 11:32:06 A facut careva D sau E, sa explice putin cum si ce au facut. Sau unde as putea gasi solutiile oficiale ?
Titlul: Răspuns: UVA Contest of Newbies 2007 Scris de: Filip Cristian Buruiana din Decembrie 30, 2007, 12:00:47 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 :). Titlul: Răspuns: UVA Contest of Newbies 2007 Scris de: Paul-Dan Baltescu din Decembrie 30, 2007, 12:16:38 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. Titlul: Răspuns: UVA Contest of Newbies 2007 Scris de: Bondane Cosmin din Decembrie 30, 2007, 12:31:06 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). Titlul: Răspuns: UVA Contest of Newbies 2007 Scris de: Bondane Cosmin din Ianuarie 06, 2008, 12:45:55 S-au pus cumva pb in arhiva lor ?
LE. Le-am gasit. |