_Inaugurăm prin acest blogpost o serie de editoriale care, sperăm noi, îşi vor face apariţia după fiecare rundă a concursului Infoarena Monthly. Scopul lor este de a augmenta latura educativa a concursului prin explicarea detaliata a solutiilor problemelor propuse. Sperăm de-asemenea ca secţiunea de comentarii să devină o platforma potrivită pentru discuţii şi feedback despre subiecte şi despre formatul concursului în sine. Suntem conştienţi că o asemenea iniţiativă apare destul de târziu, concursul fiind deja în runda cu numărul 8, însă am considerat că o atitudine de tip Las ca începem de luni, asa se face treaba n-ar fi fost foarte inspirata. Avand in vedere ca urmatorul Luni al Monthly-ului este practic in 2013. Acestea fiind zise, let s get to work._

Runda 8 a avut 91 de concurenţi înscrişi şi 79 de concurenţi care au submitat cel puţin o sursă. Echipa a subestimat însă dificultatea setului ales, astfel doar 2 concurenţi au terminat concursul având 3 probleme rezolvate, iar una dintre probleme nu a fost rezolvată corect de nimeni. Dacă ar fi să luăm ca referinţă concursurile de tip ACM, se spune că un set de probleme este bun dacă fiecare problemă este rezolvată de către cineva, dar nimeni nu rezolvă toate problemele. We re not quite there yet, dar ne străduim Ş).

Runda 8 a avut 91 de concurenţi înscrişi şi 79 de concurenţi care au submitat cel puţin o sursă. Echipa a subestimat însă dificultatea setului ales, astfel doar 2 concurenţi au terminat concursul având 3 probleme rezolvate, iar una dintre probleme nu a fost rezolvată corect de nimeni. Dacă ar fi să luăm ca referinţă concursurile de tip ACM, se spune că un set de probleme este bun dacă fiecare problemă este rezolvată de către cineva, dar nimeni nu rezolvă toate problemele. We're not quite there yet, dar ne străduim :).

h2. 'Switch':infoarena.ro/problema/switch

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 despre care vorbeam 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);