CODEWITHSUNDEEP
c++algorithmmatrix
Ilya
Ilya

Reputation: 13

Programming task: sum of submatrices

I have a problem with resolving my programming task. In fact, I resolved it, but my code don't pass some of test (time overseed).

The text of task is following:
We have a matrix that have N*N size. The first line of input contain two int: N and K. K is a number of lines that define submatrices.
Next N lines contains elements of main matrix (whitespace as delimeter of elements, \n as delimeter of lines). After that we have K lines that defines submatrices.

Definition is following:
y_l x_l y_r x_r where (x_l, y_l) is column and line of left top corner of submatrix in main matrix and (x_r, y_r) is column and line of right bottom corner of submatrix. We have to calculate sum of all submatrices and divide it into equivalence classes (submatrices are belong to one class if that sums are equal).

Output of program should be following:
three int (divided by whitespace) where first one is number of equivalence classes, second one is number of equivalence classes that have maximum elements and third one is average of sum of all submatrices.

From tests I pick up fact that problem is in calculation of sum:

while(true){
    for(int i = x_l; i <= x_r; i++)
        sum += *diff++;
    if(diff == d_end) break;
    d_start = d_start + size;
    diff = d_start;
}

But I have no idea how to optimize it. May be someone can give me algorithm or some ideas how to calculate those sums faster. Thanks.

UPDATE: Answer
After few days of searching I finally got working version of my program. Thanks to Yakk, which gave some very usefull advices.
There's final code.
Very usefull link that I strangely couldn't find before unless I ask a very specific question (bases on information that Yakk gave me) link.
I hope that my code might be helpfull for somebody in future.

Upvotes: 0

Views: 515

Answers (1)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275405

Build a sum matrix.

At location (a,b) in the sum matrix, the sum of all elements left&above (including at (a,b)) of (a,b) in the original matrix is summed.

Now calculating the sum of a submatrix is 4 lookups, one add and two subtracts. Draw a 4x4 matrix and express the bottom right 2x2 using such sums to see how.

If you double stored data you can halve lookups. But I would not bother.

Building the sum matrix requires only a modest amoumt of work if you do it carefully.

Upvotes: 2

Related Questions