Solutii Algoritmiada 2009, Runda Finala

Subsir100

Vom calcula numarul de subsiruri "interesante" din sirul obtinut prin ordonarea sirului dat folosind metoda programarii dinamice. Corectitudinea algoritmului este data de faptul ca, numarul de subsiruri "interesante" din sirul dat este egal cu numarul de subsiruri "interesante" din sirul obtinut prin ordonarea sirului dat, deoarece exista o bijectie intre multimea subsirurilor "interesante" din sirul dat si multimea subsirurilor "interesante" din sirul obtinut prin ordonarea sirului dat (Tema demonstratia).
Fie A[1...N] sirul obtinut prin ordonarea sirului dat, iar X[i] numarul de subsiruri "interesante" din sirul A[i...N], oricare ar fi i un numar natural nenul cu proprietatea i ≤ N.
Evident X[N] = 1 si X[i] = X[i+1] + X[j] + 1, unde j este cel mai mic numar natural nenul ( i < j ≤ N ) cu proprietatea ca A[j] ≠ A[i]. In cazul in care nu exista un astfel de j, adunam 0 in loc de X[j]. Relatia de recurenta se explica astfel:
Numarul subsirurilor "interesante" din A[i...N] este egal cu numarul subsirurilor "interesante" din A[i...N] care nu il contin pe A[i], plus numarul subsirurilor "interesante din" A[i...N] care il contin pe A[i]. Iar numarul subsirurilor "interesante" din A[i...N] care nu il contin pe A[i] este egal cu numarul subsirurilor "interesante" din A[i+1...N] ( A[i+1...N] nu il contine pe A[i], iar aici ma refer la termenul A[i] si nu la valoarea lui). Pentru a obtine toate subsirurile "interesante" din A[i...N] care il contin pe A[i] trebuie sa eliminam din sirul A[i...N] toti termenii care au valoarea egala cu valoarea lui A[i] ( Intr-un subsir "interesant" toate valorile sunt distincte ) si sa il adaugam pe A[i] la inceputul fiecarui subsir "interesant" din sirul ramas. La acestea se adauga sirul care contine un singur termen si anume pe A[i]. Raspunsul cautat va fi in X[1].
Desi complexitatea determinarii sirului X este O(N), complexitatea finala este O(N*logN), datorita sortarii sirului dat.

Trmax

Problema se rezolva cu ajutorul programarii dinamice. Pentru inceput vom calcula matricea A, unde A[i][j] reprezinta numarul de 0-uri consecutive avand pe ultima pozitie elementul de pe pozitia (i, j), in cazul in care acesta este nenul, sau 0 altfel. Relatia de recurenta este evidenta, A[i][j] = A[i][j-1] + 1, daca elementul este nul, A[i][j] = 0 , altfel.

Apoi se calculeaza matricea bst, in bst[i][j] se va memora inaltimea celui mai mare triunghi care are in coltul din dreapta jos elementul de pe pozitia (i, j). Relatia de recurenta este bst[i][j] = min(bst[i-1][j-1] + 1, (A[i][j] + 1) /2). Raspunsul final va fi maximul din aceasta matrice ridicat la patrat.

Ambuscada

Primul pas din rezolvarea problemei reprezinta sortarea celor N soldati dupa timp. Apoi se construieste un sir S care retine pentru fiecare moment de timp (dintre cele ale soldatilor), capacitatea maxima de efort obtinuta de exact K soldati avand timpul mai mic decat timpul actual.

Apoi avand aceste valori calculate, se poate cauta binar capacitatea maxima de efort ce se poate obtine pentru un timp mai mic sau egal cu cel dat pentru fiecare intrebare. Avand si aceasta valoare calculata, se poate cauta binar printre obiective, obiectivul cu numarul cel mai mare mai mic sau egal cu numarul calculat anterior, acesta fiind si rezultatul.

Asadar, complexitatea finala este O(NlogN + MlogN + MlogP)

Echipe2

Se observa ca pentru a minimaliza diferenta dintre cel mai mare si cel mai mic al unei multimi, se creaza o multime cu maximele fiecarei perechi, respectiv una cu minimele fiecarei perechi.

Demonstratie: Consideram ca pana la pasul i, maximele au fost introduse in multimea A, iar minimele in multimea B. Acum presupunem ca dorim ca maximul (pe care il notam cu M) dintre elementele perechii i dorim sa-l introducem in multimea B, si minimul (pe care il notam cu m) in multimea A. Evident max(B) ≤ max(A) si min(B) ≤ min(A). De aici se disting mai multe cazuri:

M > max(B), ceea ce inseamna ca dezechilibrul maxim la multimii B este M - min(B). Dar cum m ≤ M si min(B) ≤ min(A), rezulta ca
se obine un dezechilibru mai mic daca M e introdus in A si m in B.
m < min(A), cazul se trateaza exact la fel ca si cel de mai sus.
In cazul in care min(B) ≤ M ≤ max(B) si min(A) ≤ m ≤ max(A), se observa ca nu are importanta in ce multime sunt distribuite M si m, intrucat rezultatul ramane acelasi.

Prin urmare, problema se rezolva liniar, asadar complexitatea este O(N)

Electrica

O prima observatie este ca numarul total de operatii pentru a transforma configuratia in care toate becurile sunt stinse in configuratia data este egal cu numarul total de operatii necesar stingerii tutror becurilor din configuratia data.

O solutie brute-force in O(N⁴) ar fi sa parcurgem matricea si in cand intalnim un 1, atunci este clar ca el va fi capatul din stanga-sus al unui patrat, si se schimba starea tuturor elementelor din patratul de latura L, avand drept colt elementul actual.

Aceasta idee se poate imbunatati, pentru fiecare element se poate afla numarul de schimbari la care a fost supus in O(1), utilizand N cozi pentru linii si M cozi pentru coloane. Astfel, pentru fiecare element se verifica paritatea sumei dimensiunilor cozilor corespunzatoare liniei respectiv coloanei. Daca acest numar este par, atunci valoarea elementului nu se modifica, in caz contrar acesta devine 1 daca era 0, respectiv 0 daca era 1. Daca dupa aceste transformari, elementul este 1, atunci valoarea lui se schimba si indicii se introduc in coada pentru linie, respectiv pentru coloane. Atat coada pentru linie, cat si cozile pentru coloane vor contine elementele sortate, iar atunci cand diferenta dintre indicii primului element si elementului actual este mai mare decat L, atunci acel element este scos din coada.

Carpet Bomber

Intervalele date se sorteaza si apoi se impart dupa tipul lor. Apoi se aleg tipurile cate 2 si se incearca gasirea solutiei. Complexitatea este O(T² + N²). Pentru fiecare tip de bomba exista nr_i bombe de tipul respectiv, si numarul de operatii efectuate este egal cu suma nr_i * nr_j, oricare ar fi i si j in intervalul [1, T]. Suma aceasta este egala cu suma nr_i * (N - nr_i), pentru i de la 1 la T, ceea ce in total este mai mic decat N * N.

Morcovi

Problema se rezolva prin programare dinamica. Notam cu bst[i][j] = gradul de satisfactie maxim pe care il poate obtine iepurele, daca a efectuat pasii corespunzatori bitilor de 1 ai lui i, si se afla in nodul j. Se observa ca din bst[i][j] se poate ajunge in orice bst[i + 2^poz][j + Pas[poz]] si bst[i + 2^poz][j - Pas[poz]], cu poz de la 1 la P, iar al poz - lea bit a lui i este 0. Pentru fiecare stare se alege maximul posibil. Evident rezultatul va fi maximul de pe linia bst[2^P - 1].
Observatie: Pas[i] reprezinta lungimea celui de-al i -lea pas citit din fisierul de intrare.

Secv2m

O prima solutie de complexitate O(N³) ar fi alegerea tuturor secventelor de lungime L din cele doua siruri, adunarea lor, alegerea maximului din fiecare set, solutia fiind minimul acestor maxime. Insa, aceasta solutie se poate imbunatati. Astfel, vor suprapune cele doua siruri pentru fiecare pozitie astfel incat sa se obtina toate posibilitatile, si consideram sirul S care va contine A[i] + B[i]. Pentru exemplu, primele suprapuneri arata astfel:
A : 4 3 4 2 2 - - -
B : - - 3 1 3 2 5 3 2
S : - - 7 3 5 - - - -

A : 4 3 4 2 2 - - -
B : - 3 1 3 2 5 3 2
S : - 6 5 5 4 - - -

A : 4 3 4 2 2 - -
B : 3 1 3 2 5 3 2
S : 7 4 7 4 7 - -

A : - 4 3 4 2 2 -
B : 3 1 3 2 5 3 2
S : - 5 6 6 7 5 -

Solutia se obtine folosind structura de date numita Deque, folosindu-se metoda aplicata la problema Secventa.
Se observa ca exista N + M pozitii in care se pot 'aseza' cele doua siruri, iar solutia se obtine in timp liniar, asadar complexitatea finala este O(N²).

Propozitie2

Pentru fiecare dintre cele C cuvinte se poate calcula un vector ap, care retine numarul de aparitii ale fiecarui caracter. Asadar ap[i][j] = numarul de aparitii ale caracterului j in cuvantul i.

Astfel pentru fiecare pozitie din sirul initial, se poate calcula in O(SIGMA) daca exista o permutare a unui cuvant care sa se potriveasca in sir, avand ultima pozitie cu care coincide, pozitia actuala. Relatia de recurenta este evidenta, Sol[i] = suma de Sol[i-L[j]], cuvantul j se potriveste in pozitia i, iar L[j] este lungimea cuvantului j. Asadar complexitatea finala este O(N*C*SIGMA), unde SIGMA in cazul de fata este 26

Jmenoasa

Vom transforma matricea initiala astfel:

Introducem intre oricare doua elemente adiacente pe orizontala un 0 daca elementul din stanga este mai mic, un 1 in caz contrar.
Introducem intre oricare doua elemente adiacente pe verticala un 0 daca elementul de sus este mai mic, un 1 in caz contrar.
Elementele initiale ale matricei se tranforma in 0.
Completam restul matricei cu 0.

Am redus problema la determinarea celei mai mari submatrice care incepe si se termina pe coloane si linii impare si cotine numai 0 pentru o matrice avand elementele in multimea {0, 1}. Putem gasi solutia adaptand cunoscutul algoritm de determinare a submatricei de 0 avand aria maxima.

infoarena informatica de performanta