Prima rundă de calificare a concursului ONIS 2016 s-a încheiat. În cele ce urmează vom prezenta o scurtă analiză a concursului, însoţită de soluţiile oficiale ale problemelor propuse.
 
În primul rând, felicitări câştigătorilor! Mai exact, primelor cinci echipe de studenţi în ordinea clasamentului:
 
==User(user="team_name" type="tiny")==
==User(user="mafia_unibuc" type="tiny")==
==User(user="corul_barbatesc" type="tiny")==
==User(user="lookingForAChallenge" type="tiny")==
==User(user="The_Viper_The_Mountain_And_The_Imp" type="tiny")==
 
De-asemenea, primelor 5 echipe de liceu:
 
==User(user="geniucos" type="tiny")==
==User(user="tamionv" type="tiny")==
==User(user="andreiiii" type="tiny")==
==User(user="enterprise" type="tiny")==
==User(user="Spiromanii_Messi" type="tiny")==
 

*A. MaxSubSum*
Algoritmul general de determinare a submatricei de sumă maximă este prea încet pentru această problemă, având complexitate $O(N ^ 3)$. Este în schimb natural să ne gândim că putem obţine o soluţie mai rapidă dacă analizăm modul de construcţie al matricei. Astfel, analizând matricea cu colţurile $(x1, y1, x2, y2)$, observăm că suma sa este $(x2 - x1 + 1) * B[y1...y2] + (y2 - y1 + 1) * A[x1...x2]$, unde prin $T[a...b]$ am notat suma $T[a] + T[a + 1] + …. T[b]$. Această formulă ne arată, printre altele, că nu este întotdeauna optim să alegem independent liniile şi coloanele matricei bazându-ne pe subsecvenţele de sumă maximă din cele două şiruri (soluţie încercată iniţial de unii concurenţi). Uneori o subsecvenţă de sumă nemaximă, dar de lungime mare, poate fi de ajutor.

În schimb, este adevărat că dacă submatricea optimă va avea $X$ linii şi $Y$ coloane, ne intereseaza doar subsecvenţele de lungime $X$, respectiv $Y$ care au suma maximă posibilă în $A$ şi $B$. Putem precalcula uşor şirul $bestA[Length]$ = “suma maximă a unei subsecvenţe din $A$ de lungime $Length$ ” în timp $O(N^2^)$, analog pentru şirul $bestB[]$. Apoi vom itera peste toate cele $N ^ 2$ dimensiuni posibile ale submatricei şi vom reţine maximul expresiei $LineCount * bestB[ColumnCount] + ColumnCount * bestA[LineCount]$.
*B. Avioane2*