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