Problema Iepuri – OJI 2008, Clasa a 11-a

Problema Iepuri – OJI 2008, Clasa a 11-a

Rezumat

Se dau un arbore cu nn noduri și un număr kk Fiecărui nod din arbore i se asociază un număr natural cuprins între 11 și kk Orice nod diferit de rădăcină trebuie să aibă un număr strict mai mare decât tatăl său. Să se determine numărul de moduri în care pot fi alese aceste numere, modulo 3001130\,011

Soluție

Problema Iepuri este o problemă elementară de programare dinamică pe arbore. Dar nu cred că trebuie să fiți familiarizați cu acest concept pentru a înțelege soluția. În continuare, prin f(u)f(u) mă voi referi la valoarea asociată nodului uu Ideea este să notăm cu dp[u][x]\mathrm{dp}[u][x] numărul de moduri în care putem asocia numere cuprinse între 11 și kk subarborelui cu rădăcina în nodul uu astfel încât f(u)=xf(u) = x Dacă avem fixat f(u)=xf(u) = x atunci trebuie ca f(v)>xf(v) \gt x pentru orice fiu vv al lui uu De aici obținem recurența următoare:

dp[u][x]=vfii(u)y=x+1kdp[v][y]\mathrm{dp}[u][x] = \prod_{v \in \mathrm{fii}(u)} \prod_{y = x + 1}^k \mathrm{dp}[v][y]

Care se traduce în: dp[u][x]\mathrm{dp}[u][x] este egal cu produsul valorilor dp[v][y]\mathrm{dp}[v][y] unde vv este fiu al lui uu și x<ykx \lt y \le k Matricea dp\mathrm{dp} poate fi calculată ușor în cadrul unui DFS din rădăcina arborelui. Când ne aflăm în nodul uu continuăm recursiv DFS-ul în fiii lui uu pentru a obține valorile dp[v][y]\mathrm{dp}[v][y] După ce le avem pe acestea, putem folosi recurența de mai sus pentru a calcula dp[u][x]\mathrm{dp}[u][x]

Deocamdată avem complexitatea O(nk2)O(n k^2) deoarece, atunci când calculăm valoarea dp[u][x]\mathrm{dp}[u][x] parcurgem O(k)O(k) stări pentru fiecare fiu vv adică stările acelea cu y>xy \gt x Putem reduce partea asta la O(1)O(1) calculând niște sume parțiale pe parcurs. Mai exact, la finalul funcției DFS, calculăm șirul ps[u]\mathrm{ps}[u] unde ps[u][x]=y=xkdp[u][y]\mathrm{ps}[u][x] = \sum_{y = x}^k \mathrm{dp}[u][y] Noua recurență reflectă scăderea complexității la O(nk)O(nk)

dp[u][x]=vfii(u)ps[v][x]\mathrm{dp}[u][x] = \prod_{v \in \mathrm{fii}(u)} \mathrm{ps}[v][x]

Sursă C++

Un detaliu de implementare interesant este modul în care am calculat rădăcina arborelui. Având în vedere că muchiile sunt date sub forma tată-fiu, rădăcina este singurul nod care nu apare ca fiu în lista muchiilor. Prin urmare, o putem calcula drept suma numerelor naturale mai mici sau egale cu nn adică n(n+1)/2n(n + 1) / 2 minus suma fiilor din lista de muchii.

Alt detaliu important este că, pentru un nod uu aflat la adâncimea dd (începând de la 11 f(u)f(u) nu poate fi mai mic decât dd din cauza condiției f(u)<f(v)f(u) \lt f(v) Din acest motiv, atunci când inițializez cu 11 valorile dp[u][x]\mathrm{dp}[u][x] pe xx îl iau doar de la dd la kk

Nu în ultimul rând, puteam calcula șirul ps[u]\mathrm{ps}[u] direct peste vectorul dp[u]\mathrm{dp}[u] dar pentru a păstra claritatea n-am mai făcut asta.

Problema Iepuri
#include <bits/stdc++.h>
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
const int MOD = 30011;
int main() {
int n, k; fin >> n >> k;
int root = n * (n + 1) / 2;
vector<vector<int>> ad(n + 1);
for (int i = 1; i < n; i++) {
int x, y; fin >> x >> y;
ad[x].push_back(y);
root -= y;
}
vector dp(n + 1, vector<int>(k + 1));
vector ps(n + 1, vector<int>(k + 2));
function<void(int, int)> dfs = [&](int node, int dpth) {
for (int carr = dpth; carr <= k; carr++)
dp[node][carr] = 1;
for (int son : ad[node]) {
dfs(son, dpth + 1);
for (int carr = dpth; carr <= k; carr++)
dp[node][carr] = dp[node][carr] * ps[son][carr + 1] % MOD;
}
ps[node][k] = dp[node][k];
for (int carr = k - 1; carr >= 1; carr--)
ps[node][carr] = (dp[node][carr] + ps[node][carr + 1]) % MOD;
};
dfs(root, 1);
fout << ps[root][1] << '\n';
return 0;
}

Dacă ai vreo nedumerire cu privire la problema Iepuri, lasă un comentariu și te voi ajuta

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii