Încă o rundă de felicitări pentru ==User(user="team_name" type="tiny")==, singurii care au reuşit să rezolve toate cele $9$ probleme din set şi pentru ==User(user="geniucos" type="tiny")==, care a reuşit să iasă de unul singur pe locul 2, după ce o bună perioadă din concurs a condus clasamentul.

Concursul a început după cum era de aşteptat cu submisii la problema *A. MaxSubSum*. Conform tradiţiei, suprinzător de mulţi concurenţi au trimis soluţii care nu foloseau tipuri de date pe 64 de biţi. Atragem atenţia aici şi asupra faptului că tipul *long* nu are 64 de biţi pe platforma noastră. După cum puteţi citi (spre exemplu) 'aici':https://software.intel.com/en-us/articles/size-of-long-integer-type-on-different-architecture-and-os, este o soluţie mult mai bună să folosiţi mereu tipul *long long*, care nu variază la fel de mult în funcţie de arhitectură.
 
A urmat problema *F. Pokemon*, ca dovadă că enunţurile complicate nu implică soluţii complicate, o lecţie valoroasă pentru majoritatea concursurilor de informatică.
 

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