Revizia anterioară Revizia următoare
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.
AVD
Cea mai simpla solutie consta in generarea tuturor submultimilor de muchii pe care le eliminam. Ce ramane este o reuniune de componente conexe, care defineste fiecare cate o partitie. Dintre toate cele 2N-1 partitii generate, le pastram pe cele unice si impartim acest numar la numarul total de partitii (care poate fi generat si el prin backtracking sau folosind programare dinamica).
O solutie mai laborioasa consta in generarea fiecarei partitii (putin peste 100, pt N=13) si, pentru fiecare astfel de partitie (care are, sa presupunem K elemente), calcularea urmatoarelor valori: ok[i][j][S] = 1 sau 0 , reprezentand daca e posibil sau nu sa se "acopere" elementele partitiei corespunzatoare starii S ($S$ e un numar pe K biti), folosind nodurile din subarborele lui i si ramanand j noduri, inclusiv nodul i, intr-o componenta conexa pe care nu o "potrivim" peste vreun element al partitiei (si care poate fi eventual extinsa ulterior de catre un stramos al lui i); o valoare j=0 indica ca au fost folosite toate nodurile din subarborele lui i, inclusiv i, pentru a genera componente conexe care se "potrivesc" peste elemente ale partitiei. Aceste valori se calculeaza folosind programare dinamica de tip rucsac pe arbore, in functie de valorile calculate pentru fii (valori de tipul ok[fiu][j'][S'], cu j' < j si S' inclus in S). Daca ok[ 1 ][ 0 ][2K-1] are valoarea 1, atunci se poate genera o impartire in componente conexe a arborelui, ce corespunde partitiei respective.
CT
Swap
Obj
1expr
Cc
Problema cere determinarea unui cuplaj de cost minim, intr-un graf bipartit complet. Aceasta se poate realiza folosind un algoritm de flux maxim de cost minim sau, mai rapid, folosind algoritmul Ungar.
Joc3
Problema este cunoscuta sub numele de "staircase Nim".
Geometry
Itree
Hprob
Nodiv
Arbore de cicluri
Gandaci Java
Problema cere determinarea unui cuplaj maxim intr-un graf bipartit. Algoritmii "standard" pentru determinarea unui cuplaj maxim sunt prea lenti pentru limitele date, de aceea este necesara folosirea unei optimizari, cunoscuta ca algoritmul Hopcoft-Karp (aici gasiti o implementare in Python a acestui algoritm).
Roy-Floyd
Se aplica algoritmul Roy-Floyd standard, la care se adauga un criteriu suplimentar: in cazul in care se gaseste un drum de distanta egala cu distanta minima curenta, dar avand un numar mai mare de strazi, se va alege drumul respectiv.
Biomech
Expresii min-max
Expresia data poate fi evaluata folosind o metoda de complexitate liniara (O(N)). Pentru simplificarea explicatiilor, vom considera ca intreaga expresie este incadrata intr-o pereche de paranteze. Se parcurge expresia de la stanga la dreapta si se va mentine o stiva cu operatorii neevaluati inca, cu rezultate partiale si cu paranteze deschise. Cand se inalneste un operator, acesta se adauga in stiva. Cand se intalneste un operand si in varful stivei este un operator, se efectueaza operatia respectiva (caci in stiva se va gasi si cel de-al doilea operand): adica se elimina din stiva operatorul si cel de-al doilea operand si se pune in varful stivei rezultatul operatiei. Cand se intalneste un operand si in stiva se afla o paranteza deschisa, operandul se pune in varful stivei. La intalnirea unei paranteze inchise vom evalua toate operatiile pana la prima paranteza deschisa din stiva. Apoi vom inlocui paranteza deschisa cu rezultatul evaluarii si, daca pe nivelul urmator din stiva se gaseste un operator, atunci efectuam operatia. La final, in varful stivei vom avea rezultatul expresiei.
