Solutii Happy Coding 3

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 2^N-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 ][2^K-1] are valoarea 1, atunci se poate genera o impartire in componente conexe a arborelui, ce corespunde partitiei respective.

CT

Se fixeaza radacina arborelui intr-un nod (sa zicem nodul 1). Pentru fiecare din cele K perechi de orase se calculeaza LCA-ul (lowest common ancestor = cel mai apropiat stramos comun). Se poate folosi orice metoda eficienta de determinarea a LCA-ului: de exemplu, pentru fiecare nod i se pot memora O(logN) valori, stramos[i][j], reprezentand stramosul aflat cu 2^j nivele mai sus in arbore (cu j incepand de la 0), iar cu aceste valori, LCA-ul a oricare 2 noduri se poate determina in timp O(logN). Se sorteaza apoi LCA-urile tuturor perechilor, in functie de nivelul din arbore (LCA-urile de pe un nivel mai jos aflandu-se inaintea celor de pe un nivel mai ridicat). In continuare, vom parcurge LCA-urile in ordinea sortata. Pentru a rezolva problema, avem acum 2 posibilitati:

Vom renumerota nodurile conform unei parcurgeri in adancime (DF), astfel incat toate nodurile din subarborele oricarui nod i sa formeze un interval de numere consecutive. Apoi vom tine un arbore de intervale pentru aceste numere. In arborele de intervale vom memora daca un nod (identificat prin numarul asociat lui din cadrul parcurgerii DF) a fost eliminat din arbore sau nu. Pentru fiecare LCA, in ordinea precizata mai sus, vom verifica daca cel putin unul din cele 2 noduri al caror LCA este a fost deja eliminat din arbore. Daca nu a fost eliminat nici unul, vom selecta LCA-ul acestora ca oras ce va fi bombardat si vom marca ca intreg intervalul de numere corespunzator subarborelui LCA-ului a fost eliminat din arbore. Complexitatea acestei variante este O(K*logN), plus complexitatea determinarii celor K LCA-uri (care ar putea fi O(N*logN + K*logN)).
A doua varianta nu mai necesita o renumerotare si utilizarea unui arbore de intervale, insa mentine ideea de a memora pentru fiecare nod daca acesta a fost eliminat sau nu din arbore. Parcurgem LCA-urile si verificam pentru fiecare daca cel putin unul din cele 2 noduri din perechea de noduri pentru care a fost calculat LCA-ul a fost deja eliminat din arbore. Daca nici unul din cele 2 noduri nu a fost eliminat din arbore, vom selecta LCA-ul ca fiind oras ce va fi bombardat si apoi vom efectua o parcurgere DF pentru a marca toate nodurile din subarborele acestuia ca fiind eliminate. Optimizarea importanta este ca daca, in cadrul acestei parcurgeri, intalnim un nod deja marcat anterior ca fiind eliminat, nu vom parcurge subarborele acestuia. In felul acesta, fiecare nod este marcat ca find eliminat cel mult o singura data, iar complexitatea acestei etape este O(K + N).

Swap

Vom construi o permutare P a multimii {1,...,N}, asociata primului sir (N este lungimea fiecaruia din cele 2 siruri). Pentru fiecare caracter x din primul sir, vom calcula al catelea caracter de tipul respectiv este in cadrul primului sir (acest lucru se poate realiza usor in O(N)). Apoi vom construi permutarea P in felul urmator: pentru fiecare caracter x, pentru care stim ca este al y-lea caracter de tipul sau si care se afla pe pozitia i, vom seta valoarea lui P[i] ca fiind egala cu pozitia pe care se afla cel de-al y-lea caracter egal cu x din cel de-al doilea sir. Numarul de operatii swap necesare este egal cu numarul de inversiuni ale permutarii P. Acest numar poate fi determinat eficient in mai multe feluri: folosind mergesort (sortare prin interclasare), arbori de intervale, arbori indexati binar, impartirea in grupe de cate $\sqrt N$ etc.

Obj

Vom porni de la o solutie avand complexitatea O(N*K). Vom calcula win[ 0 ][ i ] = 1, daca gramada contine i obiecte, castigatorul trebuie sa stranga un numar par de obiecte, iar jucatorul aflat la mutare are strategie sigura de castig, sau 0, daca jucatorul aflat la mutare nu are strategie sigura de castig. win[ 1 ][ i ] va reprezenta acelasi lucru, cu diferenta ca cel care castiga jocul este cel care aduna un numar impar de obiecte. Avem win[ 0 ][ 0 ] = 1 si win[ 1 ][ 0 ] = 0. Pentru fiecare valoare a lui i de la 1 la N, variem numarul de obiecte pe care le ia jucatorul aflat la mutare si, in functie de paritatea acestui numar, paritatea lui i si paritatea numarului de obiecte ce trebuie luate pentru a castiga jocul, se determina starile in care se poate ajunge; ca orice alt joc rezolvat prin programare dinamica, jucatorul aflat la mutare va avea strategie sigura de castig daca cel putin una din starile in care poate ajunge este o stare de pierdere pentru jucatorul ce se va afla la mutare in continuare (adica adversarul).

Solutia O(N*K) se poate optimiza la O(N), observand ca, de fapt, pentru starile in care poate ajunge jocul dupa efectuarea unei mutari nu ne intereseaza numarul exact de obiecte ramase, ci paritatea acestui numar. Pe masura ce mergem cu i de la 1 la N si calculam valorile mentionate anterior, retinem si ultima valoare a lui i ce corespunde unei stari de tipul (x,y,z), unde x reprezinta pariatea numarului de obiecte pe care trebuie sa le ia unul din cei doi jucatori pentru a castiga jocul, y reprezinta paritatea numarului de obiecte aflate in gramada, iar z retine daca jucatorul aflat la mutare are sau nu are strategie sigura de castig in conditiile date de x si y. Memorand astfel de triplete, problema de decizie pentru un numar de obiecte i se reduce la a verifica daca ultimul numar de obiecte din gramada (ultima pozitie j < i) ce corespunde unei stari de un anumit tip care ar determina existenta unei strategii sigure de castig pentru pozitia i, se afla in intervalul [i-K,i-1] (adica acel numar de obiecte in gramada poate fi obtinut dintr-o singura mutare).

Uitandu-ne pe valorile obtinute pentru fiecare i de la 1 la N, observam o regula care reduce complexitatea rezolvarii problemei la O(1). Pentru K par, daca N mod (K + 2) = 1, castigatorul jocului va fi Ionel (al doilea jucator); in caz contrar, castigatorul va fi Gigel (primul jucator). Pentru K impar, daca N mod (2 * K + 2) = 1, atunci castigatorul este Ionel (al doilea jucator); in caz contrar, castigatorul va fi Gigel (primul jucator).

1expr

Problema se rezolva folosind programare dinamica. Pentru fiecare K de la 1 la 3⁸ se calculeaza lungimea minima a unei 1-expresii care are ca rezultat pe K, iar ultima operatie efectuata in cadrul acestei 1-expresii este +, *, ^ sau ! (deci se calculeaza 4 valori). Este important sa se calculeze toate aceste 4 valori si nu doar o singura lungime minima a unei 1-expresii care il are ca rezultat pe K, deoarece este posibil ca acea 1-expresie sa se obtina folosind operatori de prioritate mica si, pentru a fi folosita in cadrul unor expresii mai mari, sa trebuiasca pusa intre paranteze.

De exemplu, 1-expresia de lungimea minima pentru 8 este: 1+1+(1+1+1)!. O alta scriere a lui 8, care are lungimea cu 1 mai mare este: (1+1)^(1+1+1). Insa aceasta a doua reprezentare a lui 8 poate fi folosita fara a fi inclusa intre paranteze, daca trebuie inmultita cu o alta expresie, in timp ce prima scriere trebuie inclusa intre paranteze.

Programarea dinamica este implementata destul de usor (pentru un numar K):

pentru + : se incearca combinarea a doua expresii al caror rezultat este X, respectiv K-X
pentru * : combinarea a doua expresii al caror rezultat este X, respectiv K/X
pentru ^ : similar
pentru ! : numai in cazul in care K este factorialul unui numar (pentru limitele date, factorialul maxim este 7! )

Se calculeaza la inceput cele 4 valori pentru fiecare numar de la 1 la limita maxima, apoi pentru fiecare numar dat in fisierul de intrare, doar se afisaza rezultatul (daca s-ar recalcula valorile pentru fiecare numar, s-ar depasi limita de timp).

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

Pentru fiecare pereche de segmente, se determina daca acestea se intersecteaza. Daca cele 2 segmente nu sunt paralele, atunci se calculeaza punctul de intersectie al dreptelor suport al celor 2 segmente si apoi se verifica daca punctul de intersectie se afla in interiorul ambelor segmente. Daca cele 2 segmente sunt paralele, atunci se verifica daca se afla pe aceeasi dreapta (putem verifica usor acest lucru, calculand intersectia dreptelor suport cu axa OX sau OY). Daca sunt pe aceeasi dreapta, se verifica daca exista un capat al unui segment care sa aiba atat coordonata X, cat si coordonata Y, situate intre coordonatele capetelor celuilalt segment (inclusiv capetele).

Itree

Un arbore este "arbore de intervale" (conform definitiei din enunt), numai daca orice nod are cel mult 2 vecini al caror grad este mai mare decat 1.

Hprob

Se vor numerota cele 4!=24 de permutari posibile ale celor 4 obiecte cu numere de la 1 la 24. Se va calcula apoi o matrice A, unde fiecare element A[i][j] reprezinta probabilitatea ca daca un client gaseste obiectele in starea j, acesta sa le puna la loc in ordinea corespunzatoare starii i. Vom considera ca, initial, obiectele se aflau in ordinea corespunzatoare starii 1 si vom calcula probabilitatea ca la sfarsit acestea sa se afle tot in starea 1. Vom privi matricea A calculata ca o matrice de iteratie. Vom avea un vector V_i[j] reprezentand probabilitatea ca obiectele sa se afle in starea j dupa k iteratii. Putem calcula pe V_i ca fiind A*V_i-1. In felul acesta, V_N=A^N*V₀. V₀ are valoarea 1 pe pozitia 1 si 0 pe celelalte pozitii, iar A^N poate fi calculata eficient folosind exponentiere logaritmica.

Arbore de cicluri

Vom realiza urmatoarea operatie in mod repetat, pana cand operatia nu mai poate fi aplicata: daca exista un nod i avand gradul 2, iar vecinii acestuia sunt j si k, eliminam nodul i din graf si introducem muchia j-k, daca aceasta muchie nu exista deja. Daca graful dat este un arbore de cicluri, atunci la final trebuie sa ramanem cu doar 2 noduri (si, initial, numarul de noduri trebuie sa fi fost cel putin 3). Pentru a aplica operatia descrisa in mod eficient, vom folosi o coada in care vom introduce nodurile cu gradul 2. De fiecare data cand extragem din coada un nod i, exista posibilitatea sa modificam gradele vecinilor acestuia, j si k; daca j sau k ajung sa aiba gradul 2 in urma eliminarii lui i, ii introducem si pe ei in coada. Mai trebuie sa folosim o structura de date eficienta pentru a determina rapid daca 2 noduri sunt adiacente, precum si pentru a elimina noduri din "lista" de adiacenta a altor noduri (in implementarea solutiei oficiale s-au folosit arbori echilibrati, prin intermediul structurii "set" din STL).

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

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

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.

Noroc

Un punct de pornire consta in calcularea unor vectori p_i[S], reprezentand probabilitatea ca dupa i aruncari sa se obtina suma S. S ia valori intre 0 si M, iar i trebuie sa ajunga la o valoare suficient de mare IMAX, pentru ca probabilitatea cautata sa nu isi mai modifice primele 7 zecimale dupa IMAX aruncari (adica sa convearga cu precizia dorita). p_i[S] se calculeaza pe baza lui p_i-1[S-1] si p_i-1[S+1], mai putin in cazurile limita S=M si S=0, unde formula este usor diferita. Bieninteles, calculul acestor vectori nu se va incadra in limita de timp, dar, uitandu-ne la probabilitatile obtinute pentru diverse valori ale lui X si M, vom observa (sau "ghici") ca rezultatul cerut de problema este 1-X/M (ne intereseaza doar cazul X ≤ M).