fmi-no-stress-7/solutii

Soluții FMI No Stress 8

h1. FMI No Stress 7 - Soluţii
 

h1. Re:Adunare

Destul de straightforward problema, 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.

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. Dicsi

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

Problema cere aflarea lungimii celei mai lungi subsecvenţe continue din $A$ care nu îl conţine pe $B$ ca subşir şi numărarea tuturor subsecvenţelor cu această proprietate. Să presupunem că **fixăm capătul stânga** $i$. Pentru a afla cea mai lungă subsecvenţă, vom căuta iterativ primul număr din $B$, apoi, în continuare, al doilea, ş.a.m.d. Când am găsit ultimul număr din $B$ sau am ajuns la sfârşitul şirului $A$, ne oprim. Soluţia aceasta are complexitate $O(n^2^)$.
 
Pentru a o optimiza, putem parcurge şirul de la dreapta la stânga şi menţine direct legăturile la fiecare număr din şir (putem face asta, deoarece şirul $B$ conţine numere distincte). Astfel putem găsi poziţia primului număr $c$ din dreapta lui $i$. Vom ţine, mai apoi, $end[x] = "poziţia de terminare pentru sufixul din dreapta lui i care începe cu numărul x şi este cel mai din stânga$. Vom menţine o variabilă $dr$ globală, care va reţine cea mai din stânga poziţie din dreapta lui $i$ care îl conţine pe $B$ ca subşir (iniţial este egală cu lungimea şirului $A$). Avem 3 cazuri:
 
* numărul de pe poziţia $i$ este ultimul din $B$ : $end[A[i]] = i$
* numărul de pe poziţia $i$ apare în $B$ la poziţia $poz$, dar nu este ultimul : $end[A[i]] = end[B[poz + 1]]$
* numărul de pe poziţia $i$ este primul în $B$ : $dr = end[A[i]]$
 
Bineînţeles, iniţial $end$ va fi umplut cu valoarea egală cu lungimea şirului $A$.
Complexitatea acestei soluţii este liniară.
 

h1. Dlboss
O primă observaţie este că, pentru ca Dl. Boss să poată vizita fetele în ordinea strict crescătoare a frumuseţii, este suficient şi necesar ca frumuseţile acestora să fie diferite două câte două.

Vom **sorta** fetele descrescător după frumuseţe şi de vom procesa în această ordine. La fiecare pas, vom ţine mulţimea de fete aleasă, la care îi vom adăuga o noua fată. Singura problemă care poate apărea este atunci când noua mulţime de fete depăşeşte timpul maxim alocat. În acest caz, vom renunţa intuitiv la fata cea mai depărtată, după care vom continua procesul. Simularea se poate face cu un **max heap** (a.k.a. $std::priority_queue$), în timp $O(n log n)$, bineînţeles, cu atenţtie la detaliile de implementare.

Vom **sorta** fetele descrescător după frumuseţe şi de vom procesa în această ordine. La fiecare pas, vom ţine mulţimea de fete aleasă, la care îi vom adăuga o noua fată. Singura problemă care poate apărea este atunci când noua mulţime de fete depăşeşte timpul maxim alocat. În acest caz, vom renunţa intuitiv la fata cea mai depărtată, după care vom continua procesul. Simularea se poate face cu un **max heap** (a.k.a. $std::priority_queue$), în timp $O(n log n)$, bineînţeles, cu atenţie la detaliile de implementare.

h1. Hapsan

* 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ţ.
h1. Shield

Soluţia se bazează pe determinarea la fiecare pas a intervalului în care se poate afla scutul. Să-l definim ca fiind $left[i]...right[i]$. Algoritmul va fi compus din doi paşi:
 
* **Pasul 1 (forward pass)** : Pornim cu $left[$1$]$ $=$ $right[$1$] = 1$. Pentru următorii paşi, vom avea că $left[i], right[i] = left[i - 1] - 1, right[i - 1] + 1$, pe care îl vom intersecta cu intervalele $X - L + 1, X$, pentru fiecare monstru aflat la înălţimea $i$ şi coordonata orizontală $X$. Există soluţie ddacă nu am obţinut intervale vide pe parcurs.
 
* **Pasul 2 (back pass)** : Pornim de la înălţimea maximă spre $1$ şi, intersectăm în ordine intervalul $left[i], right[i]$ obţinut la pasul $1$ cu intervalul $left[i + 1] - 1, right[i + 1] + 1$ obţinut la pasul 2.
 
Pentru a construi o soluţie validă, este suficient acum să pornim de jos în sus şi să afişăm orice direcţie, atâta timp cât aceasta ne va trimite pe o coordonată validă la pasul următor (verificând cu valorile procesate mai sus).
 
**Bonus: Cum numărăm soluţiile distincte?**
 

h1. Cutit
O primă observaţie este că un lanţ de $K + 1$ noduri este o soluţie validă. Această soluţie ar trebui să obţină 15 puncte.