$ANS = p1 * p2 * p3 * ... pk$ unde $pi$ este numărul de posibilităţi de a colora al $i-lea$ semn de întrebare.

Dacă ar fi să privim matricea ca o tablă de şah, facem observaţia critică conform căreia celulele albe sunt independente complet de cele negre. Mai precis, toate căsuţele albe au doar vecini negri iar căsuţele negre au doar vecini albi. Aşa că presupunând că toate celulele albe sunt fixate (pentru fiecare $?$ de casuţă albă am ales deja culoarea) putem doar să trecem prin cele negre şi să înmulţim pentru fiecare $?$ numărul de valori pe care le poate lua semnul de întrebare respectiv, conform formulei precedente. Având în vedere că $K$, numărul de $?$, este mai mic sau egal cu $18$, atunci fie numărul de semne de întrebare albe este mai mic sau egal decât $9$, fie cel de semne de întrebare negre este mai mic sau egal decat $9$.

Dacă ar fi să privim matricea ca o tablă de şah, facem observaţia critică conform căreia celulele albe sunt independente complet de cele negre. Mai precis, toate căsuţele albe au doar vecini negri iar căsuţele negre au doar vecini albi. Aşa că presupunând că toate celulele albe sunt fixate (pentru fiecare $?$ de casuţă albă am ales deja culoarea) putem doar să trecem prin cele negre şi să înmulţim pentru fiecare $?$ numărul de valori pe care le poate lua semnul de întrebare respectiv, conform formulei precedente. Având în vedere că $K$, numărul de $?$, este mai mic sau egal cu $18$, atunci fie numărul de semne de întrebare albe este mai mic sau egal decât $9$, fie cel de semne de întrebare negre este mai mic sau egal decat $9$. Obţinem astfel o complexitate de timp $O(5 ^ (K / 2) * K).
 
Problema 4. Triangles
 
Prima soluţie care ne vine în minte are complexitate $O(N log N)$ şi nu se încadrează în timp. Pentru a ajunge la ea, realizăm ca întotdeauna are sens ca numerele alese să formeze o secvenţă continuă în şirul valorilor sortate. Pentru o anume secvenţă din şirul sortat, putem afla dacă toate cele K elemente din ea sunt bune verificând ca $v[i] + v[i + 1] >= v[i + K - 1]$. Cu alte cuvinte, verificăm ca cele mai mici două numere sa poată forma triunghi cu cel mai mare dintre ele (acesta este practic cazul limită. Daca vreun alt triplet nu îndeplineşte condiţia asta, atunci nici tripletul acesta nu o va îndeplini). Această idee se implementează foarte uşor, însă sortarea necesită timp $O(N log N). Poate dacă parsăm? Nope. Radix sort? Nope.
 
Soluţia bună are o linie in plus faţă de cea descrisă anterior. Ideea este ca de fapt nu o să avem nevoie niciodată de toate cele $N$ numere pentru a găsi o soluţie printre ele. Este suficient să păstrăm doar primele $K * log(2, Vmax)$ numere. Valoare care in cazul de faţă este egală cu $150 000$. De ce? Gândiţi-vă ce înseamnă dacă o anumită secventă $(i , i + K + 1)$ nu reprezintă soluţie. Rezultă că $v[i + K - 1] > v[i] + v[i + 1]$. Deci $V[i + K - 1] > 2 * v[i]$. Cu alte cuvinte, cât timp nu găsim soluţie, odată la cel mult $K$ numere, valorile se dubleaza. Dar numerele nu pot fi mai mari decat $10 ^ 9$, deci numărul de dublări este limitat de $log(2, 10 ^ 9)$, care este aproximativ 30. Astfel complexitatea devine $O((K log Vmax) log (K log Vmax))$, iar linia în cauză este
 
==code(c) |
n = min(n , 150 * 1000);
==