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

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 despre care vorbeam este

==code(c) |
n = min(n , 150 * 1000);