OLI Bucuresti 2006 cls XI - XII problema 2

[tmac]

reamintesc enuntul :
se da o matrice n x n (n <= 100) cu elemente nr intregi ( intre -100 si 100). se cere suma maxima a elementelor unei zone dreptunghiulare din matrice.

n^4 se poate scoate cu matrice de sume. caut pe net problema, o gasesc, solutie niciunde doar Hint: Strive for an O(n^3) algorithm. Algorithms with running time O(n^6) are worthless.

poate stie cineva acel O(n^3) si ni-l impartaseste aicea.  

[•domino]

Fixezi 2 linii , calculezi sumele pe coloane (care le preprocesezi inainte) si apoi faci varianta clasica pe vector in O(N), total O(N^3). E si un articol in GInfo ianuarie 2006 despre asta

[tmac]

thanx . ma documentez si pun in aplicare.

[cristi8]

s-a ajuns sa se dea o problema care a fost discutata in ultimul numar GInfo ?
..sper ca a fost un caz izolat..

[•greco]

Discutata sau nu in ginfo, era o problema foarte cunoscuta, data la o multime de concursuri si online-judge-uri. Cu ce e Ginfo special ?

[•svalentin]

heh.. doar eu se pare ca nu o cunosteam de nicaieri
oh well.. sper ca am implementat bine n^3...

[•DeadStar]

http://acm.timus.ru/problem.aspx?space=1&num=1146


 

[cristi8]

Pai GInfo e cea mai cunoscuta si populara revista de programare din romania printre elevii de liceu care merg la olimpiada de info.

Fiind si ultimul numar, problema asta ii avantajeaza pe cei care si-au cumparat revista. Probabil cine a luat revista a trecut mai departe, ca banuiesc ca se trece cu 100 de puncte. Si nu e greu sa isi aminteasca ideea de rezolvare.

Discutata sau nu in ginfo, era o problema foarte cunoscuta

sau invers:
Fie ea o problema cunoscuta sau nu, ea s-a discutat in ULTIMUL numar GInfo, si a ramas proaspata in memoria cititorilor.

svalentin: stai linistit, nici eu nu o stiam, de aici am aflat ca a fost in GInfo.

[•greco]

Ginfo e o resursa ca oricare alta. Din moment ce problema e cunoscuta nu conteaza daca s-a dat acolo sau oriunde altundeva; la indemana unui elev de liceu sunt si timus, si uva si celelalte site-uri.
Ma rog.. sper sa trecem.

[•cristy]

sa ne ziceti si noua rezultate

[•Cosmin]

Pe infoarena s-au dat probleme la preoni de acelasi gen insa mult mai dificile . Da oricum articolul din ginfo e super misto ).

[•domino]

Da, chiar e tare articolul din ginfo