Diferente pentru blog/onis-2016-1-editorial intre reviziile #9 si #10

Nu exista diferente intre titluri.

Diferente intre continut:

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.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.