h1. Pang

Problema cerea permutarea unui şir de noduri $A[1]...A[k]$ astfel încât să existe un drum $A[1] - A[2] - ... - A[k]$ î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 $A[1]...A[k]$ (în această ordine). Să interschimbăm acum ordinea relativă $A[i], A[j]$,cu $i < j$, aleşi arbitrar. Din condiţia de DAG, rezultă că nu există drum de la $A[j]$ la $A[i]$. 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 $A[1]...A[k]$ astfel încât să existe un drum $A[1]-A[2]-...-A[k]$ î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 $A[1]...A[k]$ (în această ordine). Să interschimbăm acum ordinea relativă $A[i], A[j]$,cu $i < j$, aleşi arbitrar. Din condiţia de DAG, rezultă că nu există drum de la $A[j]$ la $A[i]$. 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$.

h1. Snowball