Concursul Agora - Etapa Finala - Solutii

(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.

Problema 1: Drumuri

Problema cerea determinarea unei partitionari a muchiilor dintr-un graf conex in perechi disjuncte astfel ca in fiecare pereche de muchii cele doua muchii sa aiba un capat comun. Pentru orice graf conex cu numar par de muchii exista o asemenea partitionare a muchiilor. Algoritmul ce solutioneaza problema ne demonstreaza acest lucru. Putem determina pentru graful nostru un arbore partial (arbore DFS sau BFS sau care mai vreti voi). Putem lua o frunza din arborele nostru, daca ea are grad par atunci o putem elimina din arbore si toate muchiile ce aveau un capat in ea sa le imperechem doua cate doua. Daca in schimb frunza are grad impar atunci eliminam toate muchiile mai putin cea din arbore si eliminam nodul virtual din graf, dar nu si muchia asociata care devine o muchie oarecare si va putea fi eliminata cand procesam tata frunzei actuale. Singura problema ce poate aparea este cand ajungem la radacina, dar cum dintr-un graf cu numar par de muchii am eliminat la fiecare pas un numar par de muchii inseamna
ca radacina are grad par, deci problema noastra este rezolvata. Complexitatea algoritmului este O(N + M) si ca timp si ca memorie, acest algoritm poate fi foarte usor implementat ca o parcurgere DFS care dupa ce viziteaza un nod si fii sai il elimina din graf.

Problema 2: Colectie

Problema se imparte in doua bucati: Prima este determinarea numarului de cifre i care apar in scrierea numerelor de la 1 la K unde i este intre 0 si 9. Aceasta problema se poate rezolva in O(log K) cu programare dinamica, o rezolvare eficienta a fost ceruta la bacalaureat in anul 2001 deci nu e asa grea :) , o rezolvare care lua putin timp ar fi fost metoda constantelor, adica putem tine minte din 100.000 in 100.000 rezultatele partiale (aceasta abordare a fost luata de Patcas Csaba la etapa finala).
Acum avem de rezolvat o problema de obtinere a unui vector dimensiune 10 ca suma unei submultimi de vectori dati la intrare. Aceasta problema o putem rezolva cu o tehnica intalnita pe la concursuri de programare, dar care nu a devenit inca clasica. Impartim multimea de vector in doua multimi de dimensiuni n / 2 si n - n /2. Pentru prima multime determinam toate submultimile si sumele vectoriale asociate acelor submultimi, si sortam submultimile dupa acele sume. Acum pentru fiecare submultime de vectori din a doua multime obtinem o suma vectoriala sum, noi vrem sa mai adaugam ceva elemente la aceasta suma pentru a obtine un vector target ce reprezinta pentru fiecare cifra numarul de etichete necesare pentru a eticheta toate numerele de la 1 la K. Deci vom cauta binar in primul sir vectorul target - sum. Faza de sortare dureaza O(n2 * 2n) si faza de cautare binara tot atat.Astfel rezolvare are complexitatea O(2n * n2 + log K) ca timp si O(2n * n) ca spatiu.

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 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_waysi,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_waysend_x,end_y,0 + num_waysend_x,end_y,1 + ... + num_waysend_x,end_y,K. Formula de recurenta pentru problema este usor de determinat:
num_waysi,j,k = num_waysi+1,j,k-1 + num_waysi-1,j,k-1 + num_waysi,j-1,k-1 + num_waysi,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).