h1. Solutii Happy Coding 3
Concursurile Happy Coding par sa fie singurele care nu au avut parte de descrieri ale solutiilor problemelor propuse.. Desi cu intarziere, intentionez sa remediez aceasta situatie. Aceasta pagina este "under construction" momentan.
O parte din problemele date in cadrul acestui concurs (cele propuse de Mugurel Ionut Andreica) au fost folosite pentru a selecta echipele care au reprezentat Universitatea Politehnica Bucuresti la etapa regionala sud-est europeana a concursului ACM ICPC, in anul 2006.
h2. 'AVD':problema/avd
h2. 'Biomech':problema/biomech
Vom calcula matricea $A[lstart][dirstart][lfinish][dirfinish][P]$, reprezentand timpul minim pentru a ajunge de pe linia $lstart$, o coloana oarecare $X$ si privind in directia $distart$, pana pe linia $lfinish$, coloana $X + 2^P^$ (deci o coloana situata cu $2^P^$ pozitii in dreapta) si privind in directia $dirfinish$. Pentru $P = 0$, vom folosi un algoritm de drum minim. Va trebui sa avem grija ca solutia de timp minim pentru a trece de pe o coloana pe coloana imediat din dreapta ei poate presupune niste mutari "in spate", pe un numar limitat de coloane din stanga. Alegand o limita maxima de $9$ coloane in stanga si in dreapta, putem folosi algoritmul Dijkstra pe un graf ale carui stari constau din elementele unei submatrici de $5$ linii, $19$ coloane si au $8$ orientari. Pentru $P > 0$, $A[lstart][dirstart][lfinish][dirfinish][P]=A[lstart][dirstart][lintermed][dirintermed][P-1] + A[lintermed][dirintermed][lfinish][dirfinish][P-1]$. Variem linia si orientarea intermediara si pastram minimul. In mod similar, vom calcula o matrice $B[lstart][dirstart][lfinish][dirfinish][P]$, unde indicele $P$ va reprezenta sosirea pe o coloana situata cu $2^P^$ coloane la stanga coloanei de start.
Vom calcula matricea $A[lstart][dirstart][lfinish][dirfinish][P]$, reprezentand timpul minim pentru a ajunge de pe linia $lstart$, o coloana oarecare $X$ si privind in directia $dirstart$, pana pe linia $lfinish$, coloana $X + 2^P^$ (deci o coloana situata cu $2^P^$ pozitii mai in dreapta) si privind in directia $dirfinish$. Pentru $P = 0$, vom folosi un algoritm de drum minim. Va trebui sa avem grija ca solutia de timp minim pentru a trece de pe o coloana pe coloana imediat din dreapta ei poate presupune niste mutari "in spate", pe un numar limitat de coloane din stanga. Alegand o limita maxima de $9$ coloane in stanga si in dreapta, putem folosi algoritmul Dijkstra pe un graf ale carui stari constau din elementele unei submatrici de $5$ linii, $19$ coloane si au $8$ orientari. Pentru $P > 0$, $A[lstart][dirstart][lfinish][dirfinish][P] = A[lstart][dirstart][lintermed][dirintermed][P-1] + A[lintermed][dirintermed][lfinish][dirfinish][P-1]$. Variem linia si orientarea intermediara si pastram minimul. In mod similar, vom calcula o matrice $B[lstart][dirstart][lfinish][dirfinish][P]$, unde indicele $P$ va reprezenta sosirea pe o coloana situata cu $2^P^$ coloane la stanga coloanei de start.
Cu aceste matrici calculate, vom determina numarul maxim de coloane pe care le poate parcurge robotul spre stanga si spre dreapta, in timpul dat, alegand maximul dintre cele $2$ variante. Voi prezenta in continuare doar cazul deplasarii spre dreapta, cel al deplasarii spre stanga fiind similar. Vom porni de la coloana $0$ si vom mari treptat numarul de coloane pe care le poate parcurge robotul (fie acest numar $C$). Pentru fiecare valoare a lui $C$ si fiecare stare posibila $(linie,orientare)$ vom mentine timpul minim in care se poate ajunge in stares respectiva. Initial, robotul poate ajunge in $0$ unitati de timp doar in starea initiala, in celelalte stari el neputand ajunge. Vom porni cu $P$ de la valoarea maxima pentru care am calculat valori (de exemplu, aceasta valoare poate fi $61$) si il vom decrementa treptat. Presupunand ca am ajuns pana la coloana $C$, vom incerca acum sa parcurgem inca $2^P^$ coloane. Folosind matricea $A$ si cunoscand timpul minim pentru a ajunge la coloana $C$ in fiecare stare posibila, vom calcula timpul minim corespunzator fiecarei stari pentru a ajunge la coloana $C+2^P^$. Daca cel putin o stare are acest moment de timp mai mic sau egal cu durata de timp maxim data, atunci incrementam valoarea lui $C$ si vom considera momentele de timp actualizate pentru noua valoare a lui $C$. Daca pentru nici o stare nu se poate ajunge la coloana $C+2^P^$ in timp util, atunci lasam valoare lui $C$ nemodificata, nefacand nimic altceva (la urmatorul pas avand, insa, o valoare a lui $P$ cu $1$ mai mica). Valoarea finala a lui $C$ este numarul maxim de coloane ce poate fi parcurs spre dreapta in timpul dat.
Cu aceste matrici calculate, vom determina numarul maxim de coloane pe care le poate parcurge robotul spre stanga si spre dreapta, in timpul dat, alegand maximul dintre cele $2$ variante. Voi prezenta in continuare doar cazul deplasarii spre dreapta, cel al deplasarii spre stanga fiind similar. Vom porni de la coloana $0$ si vom mari treptat numarul de coloane pe care le poate parcurge robotul (fie acest numar $C$). Pentru fiecare valoare a lui $C$ si fiecare stare posibila $(linie,orientare)$ vom mentine timpul minim in care se poate ajunge in stares respectiva. Initial, robotul poate ajunge in $0$ unitati de timp doar in starea initiala, in celelalte stari el neputand ajunge. Vom porni cu $P$ de la valoarea maxima pentru care am calculat valori (de exemplu, aceasta valoare poate fi $61$) si il vom decrementa treptat. Presupunand ca am ajuns pana la coloana $C$, vom incerca acum sa parcurgem inca $2^P^$ coloane. Folosind matricea $A$ si cunoscand timpul minim pentru a ajunge la coloana $C$ in fiecare stare posibila, vom calcula timpul minim corespunzator fiecarei stari pentru a ajunge la coloana $C+2^P^$. Daca cel putin o stare are acest moment de timp mai mic sau egal cu durata de timp maxim data, atunci marim valoarea lui $C$ cu $2^P^$ si vom considera momentele de timp actualizate pentru noua valoare a lui $C$. Daca pentru nici o stare nu se poate ajunge la coloana $C+2^P^$ in timp util, atunci lasam valoare lui $C$ nemodificata, nefacand nimic altceva (la urmatorul pas avand, insa, o valoare a lui $P$ cu $1$ mai mica). Valoarea finala a lui $C$ este numarul maxim de coloane ce poate fi parcurs spre dreapta in timpul dat.
h2. 'Expresii min-max':problema/emm
