h1. Pang

Problema cerea permutarea unui şir de noduri $A1...Ak$ astfel încât să existe un drum $A1 - A2 ... Ak$ în graful orientat aciclic dat în input. O primă observaţie este că, dacă există, soluţia este **unică**. Să presupunem că există o soluţie $A1...Ak$ (în această ordine). Să interschimbăm acum ordinea relativă $Ai, Aj$,cu $i < j$, aleşi arbitrar. Din condiţia de DAG, rezultă că nu există drum de la $Aj$ la $Ai$. Deci orice soluţie va trebui să păstreze aceeaşi ordine relativă a nodurilor, de unde rezultă unicitatea. Existenţa se poate verifica cu următoarea dinamică: $dp[v] = vip[v] + max{dp[w] | (v, w) e muchie în graf}$, unde $vip[v] = 1$ ddacă există o relicvă în $v$. Acum, există soluţie ddacă există un nod $v^*^$ cu $dp[v^*^] = k$.

Problema cerea permutarea unui şir de noduri $A1...Ak$ astfel încât să existe un drum $A1 - A2 ... Ak$ în graful orientat aciclic dat în input. O primă observaţie este că, dacă există, soluţia este **unică**:
 
Să presupunem că există o soluţie $A1...Ak$ (în această ordine). Să interschimbăm acum ordinea relativă $Ai, Aj$,cu $i < j$, aleşi arbitrar. Din condiţia de DAG, rezultă că nu există drum de la $Aj$ la $Ai$, deci nu poate exista o altă soluţie cu ordinea interschimbată. În concluzie, orice soluţie va trebui să păstreze aceeaşi ordine relativă a nodurilor, de unde rezultă unicitatea. Existenţa se poate verifica cu următoarea dinamică: $dp[v] = vip[v] + max{dp[w] | (v, w) e muchie în graf}$, unde $vip[v] = 1$ ddacă există o relicvă în $v$. Acum, există soluţie ddacă există un nod $v^*^$ cu $dp[v^*^] = k$. Ordinea (unică) este dictată de sortarea topologică a nodurilor grafului.

h1. Snowball