Log in

Curs 2. Programare dinamică/ Probleme mixte - Seniori

Un păianjen se află în colțul din stânga-jos al unei table pătrate de dimensiune n×n. El vrea să ajungă în colțul din dreapta-sus. La fiecare pas, păianjenul poate să meargă un pătrat la dreapta sau un pătrat în sus. Însă păianjenul are o regulă strictă: pe tot parcursul drumului nu are voie să treacă deasupra diagonalei principale a tablei (diagonala care unește colțul stânga-jos cu colțul dreapta-sus).

Cerință:
Calculați în câte moduri diferite poate păianjenul să ajungă în colțul din dreapta-sus respectând regula modulo MOD
Catalan[n] = 1/(2n+1) * C(2n,n)

D[i][j] = in cate moduri poate ajunge painajenul la pozitia i,j

D[1][1] = 1;
D[i][j] = D[i-1][j] + D[i][j-1];
N*N

N =
()
Se dau n perechi de paranteze sa se determine cate siruri parantezate corect exista
2
()() (())
D[1] = 1;
D[i] = in cate moduri pot paranteza i perechi de paranteze
Recurenta: 
              j  
 xxxxxxx(xxxx)
   j       i-j-1
   
   D[j] * D[i-1-j]
   D[0] = 1
   for(int i = 2; i <= n; ++i)
      for(int j = 0; j <i; ++j)
          D[i] = (D[i] + (1LL * D[j] * D[i-j-1])%mod ) %mod
          
for(int i = 1; i <= n; ++i)
for(int j =1 ; j<= i; ++i)          
   D[i][j] = D[i-1][j] + D[i][j-1];
   
   
Ca sa echivalam cu catalan, trebuie sa avem 2 evenimente care sunt depdente, evenimentele devin parantezele din catalan

Event 1 -> (
Event 2 -> )

Event1 = Event2  - > la final
Event2 <= Event1 -> pe tot parcursul iterarii

Se da un sir de 109 de 0 si m operatii de tipul de la x ...y toate elementele sirului cresc cu val. La final suntem intrebari de q valori ce valoare au acestea.

3 5 7
4 8 3
Q = 3
3 8 100
3 7
Q 3
4 3
6 -7
Q 8
9 -3


https://www.infoarena.ro/problema/teams

sort(v+1,v+n+1);
for(int i = 1; i <= n; ++i) {
 a <= x + v[i] <= b; | - v[i]
   rasp += upper_bound(v+1,v+i+1, b-v[i]);
   rasp -= upper_bound(v+1,v+i+1, b-v[i]-1);  
}
cout<<rasp;

https://www.infoarena.ro/problema/panou

0 1 0
1 0 0
0 0 0

0 0 0
0 0 0
0 0 0
int modificariLinie[N];
int modificariColoane[M];
for(int i = n; i >= 1; --i)
for(int j = n; j>= 1; --j)
  if((a[i][j] + modificareLinie[I] + modificariColoane[j])%2 != model[i][j]) {
            modificariLinie[i]++;
            modificariColoana[j] ++;
  }

https://www.infoarena.ro/problema/grigo

1 4 2 3
1 2
1 4 2 3
1 4 3 2
2 4 1 3
2 4 3 1
3 4 1 2
N se afla pe ultima poztie data din sir

D[i] = cate siruri valide exista cu primele i elemente 
if(i este in vizibile)
  D[i] = D[i-1];
else
  D[i] = (i-1) * D[i-1]; 
1) Este i vizibil  => 
2) Nu este i vizibil

cout << D[n]

https://www.infoarena.ro/problema/ghiozdan

https://codeforces.com/contest/1536/problem/C

5
3
DDK
6
DDDDDD
4
DKDK
1
D
9
DKDKDDDDK

D 12
K 8

for(int i = 1; i <= n; ++i) {
  cin >> c;
    if(c == D) d++
    else
      k++;
    if(d == 0 || k == 0)
      cout<< 1;
    cmmdc == __gcd(d,k);
    F[cmmdc]++;
    cout << F[{d/cmmdc,k/cmmdc}];

}

https://infoarena.ro/problema/stiva2

cin >> n >> k;
dp[i][k] = in cate moduri poti sa pui i globuri astfel incat ai k elemente pe stiva
for(int i =1; i <= n; ++i)
  for(int j = 1; j <= k; ++k) {
    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])
  }
cout << dp[n][k];    
ans[i] = in cate moduri pot sa fac sirul pentru i elemente
for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= k; ++j) {
          ans[i] += ans[i-j] * dp[i-j][0];
        }    
}     i-j       i
1....   ....... 
abur abur X Y X Y
   X ori        
   F F G
   Dp[3][1]
   
Dp[2][2]
G F F
Dp[3][1]=Dp[3][0];


https://www.infoarena.ro/problema/disjoint

int multime(x){
  if(t[x] == x)
    return x;
  else
    return t[x] = multime(t[x]);
  
}
int h[]
void union() {
  if(h[x] > h[y])
    t[y] = x;
  else {
      t[x] = y
      if(h[x] == h[y])
        h[y]++;
      }
}  
cin >> n;
for(int i = 1;i  <= n ;++i)
  t[i] = i;
cin >> m;
for(int i = 1; i <= m; ++i) {
  cin >> test >> x >> y;
  if(test == 2) {
    if(multime(x) == multime(y) )
      cout << "DA\n";
      else
        cout << "NU\n";
  }
  else {
    union(multime(x), multime(y));
  }
}
O(N + M*log*N)
1 2    4     5  6  
        |  |     |      
       4 3    7
       
          rad
       |    |   | 
       fii   fii fii

https://www.infoarena.ro/problema/apm

M <= 300.000 => N + M*log2M

N*N

vector<int>G[N];

void dfs(int x) {
  viz[x] = 1;
  for(auto y : G[x]) {
    if(!viz[y]) {
        h[y] = h[x]+1;
        dfs(y)
        }
  }
}

cin >> N;
for(int i = 1;  i <N ; ++i) {
cin >> x>> y;
G[x].push_back(y);
G[y].push_back(x):
}
h[1] = 1;
dfs(1);

cout << h[sus] - h[jos];

}