h1. Concursul Agora - Etapa Finala - Solutii

(Creat de ==user(user="Cosmin" type="tiny")== la data de _2005-07-12_ categoria _Competitii_, autor(i) _Cosmin_)

(Categoria _Competitii_, autor(i) _Cosmin_)

Articolul contine cateva idei de solutionare a problemelor de la etapa finala a concursului Agora. Concursul s-a desfasurat la Cluj in 9 iulie pentru concurentii ce s-au calificat in finala, dar s-a desfasurat si online pentru cei care doreau sa isi incerce puterile.

==Include(page="template/raw")==

h2. Problema 1: Drumuri

h2. Problema 3: Heroes of Might and Magic

Problema cerea determinarea numarului de drumuri de la un punct ({$start_x, start_y$}) dintr-o matrice pana la un punct ({$end_x, end_y$}) din aceiasi matrice, drum care sa aiba cel mult $K$ pasi. Problema se rezolva usor folosind metoda programarii dinamice. Vom folosi o matrice tridimensionala unde $num_ways{~i,j,k~}$ are semnificatia: numarul de drumuri ce incep in ({$start_x, start_y$}), se termina in ({$i, j$}) si au fix $k$ pasi. Solutia se va afla in {$num_ways{~end_x,end_y,0~}+num_ways{~end_x,end_y,1~}+...+num_ways{~end_x,end_y,K~}$}. Formula de recurenta pentru problema este usor de determinat:
{$num_ways{~i,j,k~} = num_ways{~i+1,j,k-1~}+num_ways{~i-1,j,k-1~} + num_ways{~i,j-1,k-1~} + num_ways{~i,j+1,k-1~}$}. Se observa ca pentru a determina valorile corespunzatoare lui $k$ avem nevoie doar de valorile corespunzatoare lui {$k - 1$}, deci putem folosi doua matrici bidimensionale in loc de una tridimensionala. Complexitatea solutiei ca si timp este $O(N * M * K)$ iar ca si spatiu este {$O(N * M)$}.

Problema cerea determinarea numarului de drumuri de la un punct ({$start_x, start_y$}) dintr-o matrice pana la un punct ({$end_x, end_y$}) din aceeasi matrice, drum care sa aiba cel mult $K$ pasi. Problema se rezolva usor folosind metoda programarii dinamice. Vom folosi o matrice tridimensionala unde $num_ways{~i,j,k~}$ are semnificatia: numarul de drumuri ce incep in ({$start_x, start_y$}), se termina in ({$i, j$}) si au fix $k$ pasi. Solutia se va afla in {$num_ways{~end_x,end_y,0~} + num_ways{~end_x,end_y,1~} + ... + num_ways{~end_x,end_y,K~}$}. Formula de recurenta pentru problema este usor de determinat:
{$num_ways{~i,j,k~} = num_ways{~i+1,j,k-1~} + num_ways{~i-1,j,k-1~} + num_ways{~i,j-1,k-1~} + num_ways{~i,j+1,k-1~}$}. Se observa ca pentru a determina valorile corespunzatoare lui $k$ avem nevoie doar de valorile corespunzatoare lui {$k - 1$}, deci putem folosi doua matrici bidimensionale in loc de una tridimensionala. Complexitatea solutiei ca si timp este $O(N * M * K)$ iar ca si spatiu este {$O(N * M)$}.