fmi-no-stress-7/solutii

Soluții FMI No Stress 8

h1. FMI No Stress 7 - Soluţii
 

h1. Re:Adunare
Trebuia implementată adunarea pentru numele naturale date în formatul din teoria mulţimilor. Condiţiile iniţiale garantau că rezultatul se încadrează în limitele de memorie. Cum ordinea relativă a elementelor într-o mulţime determină o multitudine de variante de a o reprezenta, trebuia aleasă soluţia care genera şirul minim lexicografică (prioritizam afişarea elementelor mai mari înaintea celor mai mici).

h1. Blaturi

Problema se rezolvă utilizând **metoda greedy**.

Problema se rezolvă utilizând **metoda greedy**:
 

Fie $SumSt[K]$ = suma timpilor pentru a prepara blaturile de la $1$ la $K$ si $SumDr[K]$ = suma timpilor pentru a prepara blaturile de la $K$ la $N$.

Este evident că dacă studentul 1 face $K$ blaturi din cele $N$, se va plăti $SumSt[K] * Timp1$ şi $SumDr[K+1] * Timp2$. La valoarea pe care o obţinem se mai adaugă şi eventualele costuri suplimentare, costuri obţinute în funcţie de numărul de blaturi făcute de fiecare student. Deoarece dorim să minimizăm acest cost suplimentar total, deducem că trebuie să-i alternăm cât mai mult posibil pe cei doi.

Este evident că dacă studentul 1 face $K$ blaturi din cele $N$, se va plăti $SumSt[K] * Timp1$ şi $SumDr[K+1] * Timp2$. La valoarea pe care o obţinem se mai adaugă şi eventualele costuri suplimentare, costuri obţinute în funcţie de numărul de blaturi făcute de fiecare student. Deoarece dorim să minimizăm acest cost suplimentar total, deducem că trebuie să-i alternăm cât mai mult posibil pe cei doi.
 

De exemplu, dacă avem 11 blaturi şi studentul 1 face 7 blaturi (deci studentul 2 face 4 blaturi), trebuie să avem următoarea distribuţie: $121212121 11$. Astfel vom plăti de două ori costul suplimentar cerut de studentul 1.
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

* rezolvarea restricţiilor pe interval : Se poate rezolva preprocesând $left[i] = "cel mai din dreapta sushi pe care îl pot lua ca penultim, dacă ultimul sushi luat a fost i$". Se demonstrează că $left[i] = min{Aj | Aj <= i <= Bj} - 1$. Acest lucru se poate calcula în mai multe moduri : cu deque / baleiere / arbore de intervale. Există totuşi o soluţie care rezolvă problema în timp liniar, folosindu-se doar de un array ca structură auxiliară, pe care o lăsăm ca temă de gândire.

* rezolvarea restricţiilor de monotonie : Se poate rezolva în două moduri, folosind un AIB / arbore de intervale. Unul este sortând în prealabil sushi-urile crescător şi rezolvându-le în ordinea sortată, rezolvarea fiind modelată ca şi query de **maxim pe prefix**. Cea de a doua soluţie consideră rezolvarea problemei într-o nouă parcurgere stânga - dreapta a sushi-urilor şi populând $dp[i]$ cu un query de **maxim pe prefix** la momentul $left[i]$. Acest concept mai poartă numele argotic de "dinamică inainte", fiind util şi uşurând implementările în multe cazuri de probleme de programare dinamică.

* rezolvarea restricţiilor de monotonie : Se poate rezolva în două moduri, folosind un AIB / arbore de intervale. Unul este sortând în prealabil sushi-urile crescător şi rezolvându-le în ordinea sortată, rezolvarea fiind modelată ca şi query de **maxim pe prefix de poziţii**. Cea de a doua soluţie consideră rezolvarea problemei într-o nouă parcurgere stânga - dreapta a sushi-urilor şi populând $dp[i]$ cu răspunsul unui query de **maxim pe prefix de valori** la momentul $left[i]$. Acest concept mai poartă numele argotic de "dinamică inainte", fiind util şi uşurând implementările în multe cazuri de probleme de programare dinamică.

Notă: Pentru a rezolva problema de 50 de puncte, este suficientă strategia greedy de a porni de la dreapta la stânga şi de a lua mereu sushi-ul curent, dacă acesta nu contrazice restricţiile din enunţ.