Solutii Happy Coding 2

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.

Problemele date in cadrul acestui concurs au fost folosite pentru a selecta cele 3 echipe care au reprezentat Universitatea Politehnica Bucuresti la etapa regionala sud-est europeana a concursului ACM ICPC, in anul 2005.

Expresii algebrice

Vom calcula o matrie T[i][j] reprezentand numarul de arbori de evaluare a sub-expresiei dintre pozitiile i si j. Daca sub-expresia dintre aceste pozitii nu este valida (nu este parantezata corect, nu are o structura corespunzatoare de operanzi si operatori etc.), atunci T[i][j] va fi 0. In caz contrar, daca expresia dintre pozitiile i si j este inclusa intre paranteze, atunci T[i][j]=T[i+1][j-1]. Daca nu este complet inclusa intr-o pereche de paranteze, atunci exista cel putin un operator care nu este inclus in vreo paranteza. Se cauta intai operatorii ' + ' care nu sunt inclusi intre paranteze si pentru fiecare astfel de operator aflat pe o pozitie k, T[i][j] se incrementeaza cu valoarea T[i][k-1]*T[k+1][j]. Daca nu se gaseste nici un ' + ' neinclus intre paranteze, atunci se cauta un ' * ' si se realizeaza aceleasi operatii.

Calatorie interplanetara

Vom calcula C[i][j] reprezentand consumul minim pentru ca nava spatiala sa ajunga la planeta i si sa fi parcurs j unitati de timp cu superviteza. Valoarea lui j este cel mult 500. C[i][j] se calculeaza pe baza lui C[i-1][j] (daca intre planetele i-1 si i nava a calatorit cu viteza normala) sau pe baza lui C[i-1][j-H_i-1] (daca intre planetele i-1 si i nava a calatorit cu superviteza), alegandu-se varianta minima dintre cele doua posibilitati.

Razboiul lumilor

Solutia optima are complexitate O(N) si se realizeaza parcurgand arborele de 2 ori. La prima parcurgere fixam radacina arborelui in nodul 1. Vom calcula pentru fiecare nod i cate 2 valori: lungimea maxima a unui drum de la orasul i la orice alt oras din subarborele acestuia, L₁[i], si lungimea maxima a unui drum de la orasul i la un oras din subarborele acestuia, dar care este diferit de primul drum, L₂[i] (practic, a doua lungime maxima a unui drum, care poate fi, eventual, egala cu lungimea primului). In a doua parcurgere vom calcula distanta maxima de la fiecare oras i la orice alt oras si vom alege orasele pentru carea aceasta distanta maxima este minima. Pentru radacina arborelui am calculat deja aceasta valoare din prima parcurgere. Pentru orice alt nod i, distanta maxima de la i la orice alt oras este ori L₁[i], ori un drum ce trece prin parintele lui i. Cel mai lung drum ce trece prin parintele lui i are lungimea egala cu distanta de la i la parintele lui i plus L₁[parinte[i]], in cazul in care drumul corespunzator lui L₁[parinte[i]] nu trece prin orasul i, respectiv plus L₂[parinte[i]], in cazul in care drumul corespunzator lui L₁[parinte[i]] trece prin orasul i.

A doua solutie are complexitatea O(N*logN) si este o generalizare a solutiei pentru cazul in care toate muchiile arborelui au aceeasi lungime. Solutia pentru cazul muchiilor cu lungimi egale are complexitate O(N) si se bazeaza pe o eliminare repetata a tuturor frunzelor din arbore. Se elimina primul strat de frunze, obtinandu-se un arbore mai mic, apoi se repeta procedeul pana cand arborele ramas are unul sau doua noduri (aceste noduri fiind nodurile cautate). In cazul in care muchiile au lungimi diferite, vom privi arborele dinspre exterior spre interior. Fiecarui nod i din arbore ii corespunde un subarbore care are toate nodurile mai aproape de exterior decat nodul i. Vom elimina si de aceasta data frunzele, pe rand. Pentru fiecare nod i vom calcula dmax[i] ca fiind lungimea celui mai lung drum de la nodul i la o frunza din subarborele sau (aceasta valoare reprezinta distanta nodului i fata de exteriorul arborelui). La fiecare pas vom elimina un nod i ramas frunza (deoarece toate nodurile din subarborele sau au fost deja eliminate anterior) pentru care dmax[i] este minim (eliminam frunza cea mai apropiata de exteriorul arborelui initial). Repetam procedeul pana cand ramanem cu un nod sau cu 2 noduri. Pentru a obtine complexitate mentionata putem folosi un heap.

Divizor si multiplu

Se vor determina toti divizorii primi ai lui x si ai lui y, impreuna cu puterile la care apar. Fiecare divizor prim al lui x trebuie neaparat sa fie un divizor prim si al lui y, la o putere mai mare sau egala. Vom calcula D=numarul de divizori primi care apar la o putere mai mare in y decat in x (inclusiv acei divizori care apar in y si nu apar deloc in x). Numarul de perechi ordonate care il au pe x ca cel mai mare divizor comun si pe y ca cel mai mic multiplu comun este 2^D.

Palindroame

Pentru a avea solutie este necesar ca cel mult un singur caracter sa apara in sir de un numar impar de ori. In mod evident, nu vom inversa niciodata o pereche de caractere alaturate identice. Din acest motiv, in cadrul palindromului pe care il vom obtine, prima aparitie a unui caracter va fi "imperecheata" cu ultima aparitie a acelui caracter, a doua aparitie cu penultima s.a.m.d. In felul acesta, fiecare pereche defineste un interval (a,b), a reprezentand pozitia caracterului din stanga din cadrul perechii, iar b reprezentand pozitia caracterului din dreapta din cadrul perechii. Singura conditie pentru ca numarul de inversiuni sa fie minim este sa nu ajungem sa inversam niciodata intre ele capetele a 2 intervale care sunt incluse unul intr-altul. Pornind de la aceasta observatie, putem alege mereu intervalul corespunzator primului element al sirului si sa ducem pe ultima pozitie a sirului capatul dreapta al acestui interval, ramanand apoi cu un sir mai mic. In cazul in care primul element al sirului este caracterul ce trebuie sa se afle in mijlocul palindromului (pentru numar impar de caractere), atunci vom alege intervalul ce corespunde ultimei pozitii a sirului. Vom repeta acest procedeu pana cand ramanem cu un sir de lungime 0 sau 1.

Lungimi de interval

Vom sorta crescator intervalele dupa capatul stanga si apoi le vom parcurge in aceasta ordine. Vom mentine 2 valori: L, reprezentand lungimea curenta, si X, reprezentand punctul cel mai din dreapta pana la care am "acoperit" cu intervale axa OX. Vom initializa valoarea lui L cu 0 si valoarea lui X cu o valoare negativa (minus infinit). Pe masura ce parcurgem intervalele, avem 3 situatii:

• capatul stanga al intervalului curent este mai mare decat X sau egal cu el => adunam la L lungimea intervalului curent si setam pe X la valoarea capatului dreapta al intervalului
• capatul stanga al intervalului curent este mai mic decat X, iar capatul dreapta al acestuia este mai mic sau egal cu X => nu realizam nici o actiune si mergem mai departe
• capatul stanga al intervalului curent este mai mic decat X, iar capatul dreapta al acestuia este mai mare decat X => adunam la L diferenta dintre capatul dreapta al intervalului curent si X, iar apoi setam pe X la valoarea capatului dreapta al intervalului curent.

Resturi

Vom calcula numarul cerut in mod incremental. La pasul i vom avea calculat numarul Q, reprezentand cel mai mic numar care respecta primele i relatii (deci Q mod p_j=r_j pentru orice j ≤ i). La pasul 1, Q este egal chiar cu r₁. Avand calculat numarul Q la pasul i, va trebui sa determinam numarul Q' la pasul i+1 care respecta primele i+1 relatii. Acest numar Q' este de forma Q + x*M, cu x ≥ 0, unde M este cel mai mic multiplu comun al numerelor p₁,...,p_i (fiind numere prime, M este chiar produsul lor). Ideea din spatele acestei formule este ca la numarul Q trebuie adunat un multiplu al numarului M, pentru ca numarul obtinut Q' sa pastreze aceleasi resturi la impartirile la primele i numere prime date. Avem acum urmatoarea ecuatie: Q + x*M = r_i+1 (mod p_i+1). Trecand pe Q in partea dreapta, obtinem o ecuatie de forma A*x = B (mod P), care se poate rezolva direct, folosind algoritmul lui Euclid extins, pentru a calcula inversul multiplicativ al lui A, relativ la numarul prim P. O metoda mai simpla de rezolvare a ecuatiei se bazeaza pe a incerca toate valorile posibile pentru x, intre 0 si p_i+1-1, care functioneaza deoarece valorile numerelor prime sunt relativ mici (mai mici decat 1000).

Aceasta problema este cunoscuta si ca Teorema chineza a restului .

Curse de cai

Vom sorta caii lui Gigel si Ionel in ordine descrescatoare si ii vom renumerota conform acestei ordini. Vom considera ca Gigel decide pentru fiecare cal al lui Ionel, in ordinea sortata, ce cal de-al sau sa ii opuna in cursa. Solutia prezentata in continuare se bazeaza pe urmatoarea observatie. Sa presupunem ca Gigel a decis ce cai de-ai sai vor concursa impotriva primilor i cai ai lui Ionel si urmeaza sa decida pentru al i+1-lea cal. Singurele doua variante fezabile pe care le are Gigel este sa aleaga cel mai bun cal al sau (dintre cei ramasi) si sa il puna sa concureze cu al i+1-lea cal al lui Ionel sau sa aleaga cel mai prost cal al sau. Vom calcula o matrice C[i][j] reprezentand costul maxim pe care il poate obtine Gigel daca i-au mai ramas caii de la i la j (asta inseamna ca toti caii de la 1 la i-1 au fost deja selectati si la fel si toti caii de la j+1 la N; de aici rezulta ca Gigel a ales dja adevrsai pentru primii N - j + i - 1 cai de-ai lui Ionel si acum trebuie sa aleaga adversar pentru urmatorul cal al lui Ionel). C[i][j] se calculeaza pe baza lui C[i+1][j] (daca Gigel alege cel mai bun cal al sau impotriva calului curent al lui Ionel) sau pe baza lui C[i][j-1] (daca elege cel mai prost cal al sau), alegandu-se varianta de cost maxim.

Cercuri

J-Arbore