Vom aborda problema cu ajutorul tehnicii de "Flux maxim":http://www.infoarena.ro/problema/maxflow. Astfel, construim o retea in care fiecare sistem solar $i$ are asociat nodul $i$, iar fiecare uniune comerciala $j$ nodul $N + j$. Sursa si destinatia vor fi alese convenabil astfel incat sa nu se suprapuna cu nodurile necesare. Vom trage un arc de la sursa la fiecare sistem solar $i$ printr-o muchie de capacitate $solarSystemTribute[i]$, cat si un arc de la fiecare planeta la fiecare dintre uniunile comerciale din care face parte, cu capacitate $INFINIT$. In final, tragem arcuri de la uniunea comerciala $i$ la destinatie, de capacitate $unionTribute[i]$. Ramane sa rulam algoritmul de flux pe acest graf, iar fluxul maxim rezultant reprezinta solutia problemei.

Complexitate timp: $O(N^5)$ (supraestimata).

Complexitate timp: $O(N^5)$ (daca se implementeaza cu Edmonds-Karp, mai putin daca se foloseste push-relabel).

Complexitate spatiu: $O(N^2)$.
h1(#Revolta). 'D. Revolta':problema/revolta

Complexitate timp: $O(N)$.
Complexitate spatiu: $O(N)$.

Descrierea solutiei **Stefan Ciobaca**
 
Funcţia wtf calculeaza minimul din vector in timp exponential in cazul cel mai nefavorabil (cand minimul este pe ultima pozitie). Ce e interesant este ca functia nu este inventata: la un laborator de Programare Functionala, un student (bun) a scris, din greseala, o functie care calculeaza minimul dintr-o lista in timp exponential, similara cu functia C de mai jos.
 
Observam ca variabila count tine minte numarul de apeluri ale functiei wtf, modulo 19997.
 
== code(cpp) |
int wtf(int i)
{
  count++;
  if (count >= 19997) {
    count -= 19997;
  }
  if (i == n - 1) {
    return a[i];
  }
  if (a[i] < wtf(i + 1)) {
    return a[i];
  } else {
    return wtf(i + 1);
  }
}
==
 
Pentru a rezolva problema intr-o complexitate buna, este necesar sa eliminam al doilea apel, redundant, la wtf(i + 1):
 
== code(cpp) |
int wtf_better(int i)
{
  count++;
  if (count >= 19997) {
    count -= 19997;
  }
  if (i == n - 1) {
    return a[i];
  }
  int cache = wtf_better(i + 1);
  if (a[i] < cache) {
    return a[i];
  } else {
    return cache;
  }
}
==
 
In acest moment, am eliminat ineficienta, dar valoarea lui count nu mai este corecta (numara cate apeluri face functia wtf_better, nu wtf). Pentru a calcula valoarea corecta a lui count, este suficient sa tinem minte si un tablou memo[], unde memo[i] tine minte cate apeluri ar fi luat wtf(i):
 
== code(cpp) |
int wtf_even_better(int i)
{
  memo[i] = 1;
  if (memo[i] >= 19997) {
    memo[i] -= 19997;
  }
  if (i == n - 1) {
    return a[i];
  }
  memo[i] += memo[i + 1]; // simulez primul apel la wtf(i + 1)
  if (memo[i] >= 19997) {
    memo[i] -= 19997;
  }
  int cache = wtf_even_better(i + 1);
  if (a[i] < cache) {
    return a[i];
  } else {
    memo[i] += memo[i + 1]; // simulez al doilea apel la wtf(i + 1)
    if (memo[i] >= 19997) {
      memo[i] -= 19997;
    }
    return cache;
  }
}
==
 
Rezultatul este in memo[ 0 ] dupa apelul la wtf_even_better(0).
 
Solutia de mai sus se poate obtine aproape mecanic, fara a intelege codul initial. Tot mecanic se poate obtine si solutia iterativa, care completeaza tabloul memo[] de la stanga la dreapta in timp ce calculeaza minimul din vector. Si solutia recursiva si cea iterativa pot fi vazute ca exemple simple de programare dinamica.
 

h1(#Sate2). 'H.Sate2':problema/sate2
Problema cere o partitionare in $k$ subseturi a caror suma sa fie egala. Aceasta problema este NP completa. Considerand restictiile problemei, putem folosi metoda Greedy. Aceasta nu va gasi mereu rezultatul dorit, dar ne marim sansele daca rulam mai multe greedy-uri diferite si vedem daca macar una gaseste o partionare buna. O alta idee ar fi sa folosim metoda Monte Carlo, se extragem un element la intamplare din rucsacul cel mai greu si sa-l mutam in rucsacul cel mai usor, astfel incat sa nu depasim greutatea necesara fiecarui rucsac, si anume $m / k$, pana ne epuizam un numar de pasi stabilit prealabil sau am gasit o solutie.

Facand abstractie de la restrictiile problemei, rezolvam folosind metoda programarii dinamice pentru fiecare caz, $k = 3$: $dp[i][j][p] = 1$ sau $0$ daca putem obtine, folosind primele $i$ obiecte, o partionare astfel incat primul rucsac are greutatea $j$, al doilea greutatea $p$, iar evident al treilea va avea greutate $m - j - p$. Se procedeaza similar pentru cazul cu $k = 4$. Toate solutiile mentionate iau punctaj maxim.

Facand abstractie de la restrictiile problemei, rezolvam folosind metoda programarii dinamice pentru fiecare caz, $k = 3$: $dp[i][j][p] = 1$ sau $0$ daca putem obtine, folosind primele $i$ obiecte, o partionare astfel incat primul rucsac are greutatea $j$, al doilea greutatea $p$, iar evident al treilea va avea greutate $m - j - p$. Se procedeaza similar pentru cazul cu $k = 4$.
 
Toate solutiile mentionate iau punctaj maxim.

h1(#Politie). 'I. Politie':problema/politie

Complexitate timp: $O(NlogN)$.
Complexitate spatiu: $O(N)$.

h1(#Padure2). 'K. Padure2':problema/padure2

h1(#Padure2). 'K. Padure2':problema/padure2
 
Se observa ca numarul de moduri prin care se poate ajunge din (i1,j1) in (i2,j2) fara a baga in seama obstacolele este
Combinari(n, k) unde n = (i2 – i1) + (j2-j1), iar k = (i2-i1).
Stiind acest lucru putem defini o functie f(i1, j1, i2, j2) care calculeaza numarul de moduri prin care se poate ajunge din (i1,j1) in (i2,j2) fara a baga in seama obstacolele.
Sortam punctele in functie de diagonala secundara.
Fie un vector nr[i] = numarul de moduri prin care se poate ajunge din (1,1) in (l[i], c[i]), fara a trece printr-un obstacol.
Recurentapentru acest vector v-a fi:
 
!onis-2016/solutii-runda-2?padure2_formula.png!
 
La final trebuie calculat dupa aceeasi regula pentru n,m.
 

public

protected