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

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.