Diagonale

Avem de calculat suma fiecarei diagonale si sa gasim maximul dintre ele. Observam ca pentru fiecare diagonala elementele ei respecta o anumita conditie si anume:

1) pentru o diagonala paralela cu diagonala principala, elementele ei au diferenta dintre randul si coloana pe care se afla constanta (adica i - j = k, k - constant, unde i e randul si j e coloana pe care se afla elementul)

2) pentru o diagonala paralela cu diagonala secundara, elementele ei au suma dintre randul si coloana pe care afla constanta (adica i + j = k, aceleasi notatii)

Pentru simplitatea implementarii vom calcula in dp[k] si ds[k] suma tuturor celulelor care respecta proprietatile 1) respectiv 2) pentru toate valorile posibile ale lui k.

Pseudocod:

diagonale(A[1..n,1..n])
   dp[1..2*n-1] <- 0  // initializam tablourile cu 0
   ds[1..2*n-1] <- 0
   for i <- 1, n do   // fiecare celula o adaugam la suma diagonalelor de care apartine
      for j <- 1, n do
         // adaptam valorile ca sa se incadreze pe acelasi interval
         dp[n + i - j] <- dp[n + i - j] + A[i,j] // -(n-1) <= i - j <= n-1 | +n  ==> 1 <= n + i - j <= 2*n-1
         ds[i + j - 1] <- ds[i + j - 1] + A[i,j] //      2 <= i + j <= 2*n | -1  ==> 1 <= i + j - 1 <= 2*n-1
      end for
   end for
   dmax <- -INFINIT // il initializam pe dmax cu o valoare <= -1000000000
   dmax <- max(dp[1..2*n-1], ds[1..2*n-1]) // aflam maximul dintre sumele diagonalelor
   return dmax

StringRepair

Observam ca fiecare litera din sirul B are un corespondent in sirul A datorita modului in care au fost obtinute sirurile. Astfel, parcurgem sirul B si pentru fiecare pozitie i din B gasim prima pozitie j din A astfel incat B[i] = A[j] si A[j] nu e corespondentul unei litere anterioare din B. A doua conditie o putem satisface prin faptul ca de fiecare data incepem cautarea in A imediat dupa j-ul anterior.

Pseudocod:
rezolvare(A[1..m], B[1..n])
   j <- 1
   for i <- 1, m do
      while B[i] != A[j] do
         j = j + 1
      end while
      // am gasit corespondentul lui B[i] ca fiind A[j],
      // deci pozitia j din A nu a fost stearsa
      write j
      // pentru i + 1 vom incepe cautarea de pe pozitia urmatoare, adica j + 1
      j = j + 1
   end for

Stiva2

O prima observatie care trebuie facuta este ca, conditia cum ca un element intrat la pasul i trebuie sa iasa la pasul cel mult i+K, implica faptul ca stiva este goala o data la maxim K pasi. De aici se contureaza o idee de dinamica:

A[i]=nr de posibilitati ca dupa i mutari stiva sa fie goala.

Pentru recurenta ne putem gandi ca fixam ultima pozitie j la care stiva era goala si ca mai inseram niste elemente in interv (j+1,i) a.i. la orice pas j+1<=t<i stiva nu este goala. Se mai observa ca pozitia j trebuie sa respecte propietatea ca (i-j)<=K (din prima observatie)

Pentru a calcula nr de posib de a introduce i elemente a.i. stiva sa nu fie goala pe parcurs si sa fie goala la final se poate calcula o noua dinamica:

B[i][j]=nr de posibilitati ca dupa i mutari sa am j elemente inca nescoase din stiva. Recurenta pentru aceasta dinamica se poate calcula usor luand in calcul cele 2 cazuri posibile pt al i+1-lea element(ori e de acelasi tip cu elementul din varful stivei si se adauga la final,ori sunt de tipuri diferite si elimina si elementul din varf)

Cu aceasta dinamica calculata putem reveni la calcularea primei dinamici(nr de posibilitati de a introduce i elemente in stiva a.i. aceasta sa nu fie goala pe parcurs,dar sa fie goala la final este in mod evident B [i] [0])

Raspunsul va fi reprezentat de A[n]

Graf2

Prima observatie necesara rezolvarii problemei este faptul ca numarul minim de arce necesare pentru a realiza 'tare-conexitate'(drum intre oricare 2 noduri) intre K noduri este exact K, deoarece un ciclu care cuprinde toate nodurile este suficient, iar o solutie cu mai putin de K arce nu este posibila (fiecare nod trebuie sa aiba cel putin un arc care porneste din el). Daca K = 1, numarul de arce necesar este evident 0.
Astfel, realizam impartirea grafului A in componente tare conexe iar pentru fiecare componenta adaugam dimensiunea sa la raspuns.

In continuare ne vom referi doar la graful componentelor tare conexe(graful obtinut prin comprimarea unei componente tare conexe intr-un sigur nod). Acest graf este, evident, aciclic.
Vom sorta topologic acest graf si vom procesa fiecare nod in ordinea inversa a sortarii, dinspre nodurile terminale spre nodurile sursa. Pentru un anumit nod, fie el X, este suficient sa asiguram drumurile catre fiii sai din A, deoarece acestia la randul lor au urmasii accesibili, fiind procesati in prealabil. Vom procesa fiii lui X in ordinea sortarii topologice, de la cei mai 'inalti' catre cei de jos. Daca ajungem la fiul i, iar acesta nu este accesibil din X, vom duce muchie directa X -> fiu(i) in B dupa care vom actualiza lista de noduri accesibile din X cu lista nodurilor accesibile din fiu(i). Acest lucru se poate face printr-un DF pornit din fiu(i) sau printr-o operatie OR, daca listele se implementeaza cu bitset.

Aceasta solutie garanteaza numarul minim de arce, deoarece adaugarea unui arc nou in B se face doar in ultima instanta (daca fiul respectiv nu poate fi accesat prin alti fii ai lui X mai inalti decat el).
Complexitatea acestei solutii este O(N * M). Atat varianta cu DF-uri cat si cea cu matrice de drumuri, tinuta pe bitset sau nu, se incadreaza lejer in timp.