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.

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

O primă idee care poate rezolva această problemă este cea de a descrie un graf cu 16 noduri (fiecare matrice posibila) şi 4 arce care ies din fiecare nod (transformarile posibile). Astfel, se poate face un DFS pe acest graf pentru a se afla daca exista conexitate intre matricele date in input. Dacă problema ar fi cerut şi numărul minim de operaţii necesare, soluţia ar fi fost dată de o parcurgere în lăţime.

Prima soluţie este mai flexibilă, iar corectitudinea ei nu depinde niciodată de particularităţile transformărilor sau ale matricelor, putând fi folosita şi pentru matrice de $N x N$. Ea are complexitate $O(2 ^ N * M)$, unde $M$ este numărul de transformări posibile. Cea de a doua soluţie are însă complexitate $O(1)$ şi se scrie in 2 rânduri.

h2. Cifre3.

h2. 'Cifre3':infoarena.ro/problema/cifre3

Această problemă avea în primă fază alt enunţ, iar cele 2 surse oficiale au la baza ideea problemei iniţiale. Astfel, marea majoritate a concurenţilor a ajuns să aiba o soluţie mult mai scurtă şi mai eficientă. Soluţia noastră se folosea de faptul ca numărul produselor posibile nu este foarte mare, din 2 motiveŞ

Demonstraţia o lăsăm ca tema acasă. Extindeţi raţionamentul de mai sus, potrivit căruia numerele de lungime $L$ produc aceleasi produse ca numerele de lungime $L - 1$ şi, pe lângă acestea, unele noi pe baza celor vechi.
De notat că deşi soluţia lui Rareş (ca şi cea a comisiei..) este mai complexă şi mai greu de codat, are avantajul că necesită un timp scurt de gândire, fiindca este practic un brut. Alegerea unei soluţii nu neaparat eficiente sau scurte, dar care rezolvă problema în restricţiile date este uneori de preferat în dauna unei implementări simple cu idei uşor mai complicate, mai ales într-un concurs de tip Monthly, Codeforces, sau TC SRM.

h2. Culori4

h2. 'Culori4':infoarena.ro/problema/culori4

bq. Deci contribuţia problemei ăsteia la concurs a fost o coloană de $0$ adaugată în clasament?

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

h2. Triangles

h2. 'Triangles':infoarena.ro/problema/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.