Soluții FMI No Stress 7

Soluții FMI No Stress 8

* 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 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 pe 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ă.

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