MATSUM - Explanation

Can somebody explain me how to speed up my solution. I used O ( 1 ) for SET function , and O ( N ^ 2 ) for SUM function, but it's , as I guess, not enough. : - (

Thanks in advance,

Aleksandar.

try using BIT,
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Thanks, I'll give it a try. :)

or use fenwick, I'll write code when I come home...

lol,
BIT == Fenwick tree
;)

just use cumulative tables or binary indexed trees in 2D..

gates gave you nice tutorial on english, and here is on serbian http://www.dms.org.yu/problem_of_month/informatics/Kumulativne tabele Januar 2008 A.pdf ..

Thanks. ;)

@gates:
lol, bit = fenwick = logaritamska xd

why 3 names for same thing ?

AFAIK,
BIT is some kind of official name.
fenwick is name of man who "innovated" it.
logaritamska is name in croatia.

Yes, that is true about Binary Indexed Trees. In Serbia it is called 'kumulativne tabele' :D

Can someone look at my code for matsum because I cannot find mistake?
It fails for test 5 and 7 ( wrong answer ).
Other tests are working, I used 2D BIT.

the problem is in your get function.
it returns the value of a square (x1,y1)(x2,y2) + values of the rectangles (x1,0)(x2,y1-1) & (0,y1)(x1-1,y2)

Thanks , I didn't write get function good.
It works now. :D

What does it mean...Exit code not zero ?
A few of my tests are okay, but some of them says Exit code not zero ..
:?:?

exit code not zero, is when your program terminate because of some error
for example. you have array a with 100 elements and you are trying to access 110th element.

Ooooks :)
Thanks :)

It seems that I have a lot of errors in my code. I have only 2 or 3 tests correct.
Can someone of the admins tell me where are my mistakes :?

gigac:
you have TLE, which means your program is too slow... Try to calculate complexity: you have 3 loops: for each query, for each row, for each cell in that row, sum that number, and print the sum...
So your complexity is: O(width*height*queries);
width = height = 1024 and there are about 10000 queries, so it is: 1024^2*10000 which is about 10^10...
that's to high, because an average computer can do about 10^8 operations per second, so your program tooks about 100 seconds to run, and limit is 1/2 second :)

You can solve this problem easily by using BIT (Binary Indexed Tree -> http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees). You have a section down there called 2D BIT... I suggest you to solve couple tasks with 1D (ordinatley) BIT

Can someone check what is wrong with my code for MATSUM? It gets AC when submitted to SPOJ but gets the last case WA in z-training.

Try with long long int (for Sum).

Thanks for replying but even after changing sum to long long I still get WA for last case. I can't possibly change the BIT to long long since that will exceed the memory limit.

I am not using C (...Pascal and have problem with english language), but I see T.L.E.
Problem is in line:

num -= (sum(x,y)+sum(x-1,y-1)-sum(x-1,y)-sum(x,y-1));

delete it and try with
...
val[1024][1024]
...

int x,y,num, upd;
scanf("%d%d%d",&x,&y,&num);
++x; ++y;

upd = num - val[x][y]
while(x <= N) {
int ty = y;
while(ty <= N) {
bit[x][ty] += upd;
ty += (ty & -ty);
}
x += (x & -x);
}
val[x][y] = num;
......
I hope you understand me.

When I do that I get MLE. :( Only 8MB of memory given. And the latest TLE is due to me using cout. It runs in time when I use printf instead.

But, I see solutions with

int bit,val [1024][1024]

int val[ 1024 ][ 1024 ] will take 4 MB of memory

Yes but the BIT takes another 4 MB of memory.

hmm I've done this task without BIT but I think it wouldn't pass on SPOJ.pl

Did you use an O(N^2) algorithm? I think that's possible but I was trying to implement 2D BIT for the first time :P

Anyway, I'm getting a WA rather than a TLE so I think there's no need to add in the val[1024][1024] array...Does anyone have any ideas why it gets WA?

Well I've done it with n^2 algorithm for summing but with optimizations like remembering the last value bigger then zero in every row.

@mister
Your code, bit corrected:

#include <iostream>
using namespace std;
short bit[1026][1026] = {{0}};
short nvl[1025][1025] = {{0}};
char cmd[4];
long long sum(int x,int y) {
  long long r = 0;
  while(x) {
    int ty = y;
    while(ty) {
      r += bit[x][ty];
      ty -= (ty & -ty);
    }
   x -= (x & -x);
  }
  return r;
}
int main() {
  int N;
  scanf("%d",&N);
  while(scanf("%s",cmd) == 1) {
    if(cmd[0] == 'E') break;
    if(cmd[1] == 'E') {
      // set
      int x,y,num, newval;
      scanf("%d%d%d",&x,&y,&newval);
      ++x; ++y;
//      num -= (sum(x,y)+sum(x-1,y-1)-sum(x-1,y)-sum(x,y-1));
      num = newval - nvl[x][y];
      nvl[x][y] = newval;
      while(x <= N) {
        int ty = y;
        while(ty <= N) {
          bit[x][ty] += num;
          ty += (ty & -ty);
        }
        x += (x & -x);
      }
    }
    else {
      // sum
      int x1,y1,x2,y2;
      scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
      ++x2; ++y2;
      printf("%d\n",sum(x2,y2)+sum(x1,y1)-sum(x1,y2)-sum(x2,y1));
    }
  }
}...

I am not using C (...Pascal, so don't know details about int, short, long in C or C++), but this work.

@Matteo123

Look discussions on your post MATSUM.

can you give me a link

@Matte0123

http://www.z-trening.com/new/www/html/submit.php?submit=7100050588&discuss=1&ref_id=7100050588&view_topic=111668

@halil
Thanks I get AC now! The bounds for num are not stated so I did not think of using short. But why is it not possible to obtain the current number on a cell using this method:

sum(x,y)+sum(x-1,y-1)-sum(x-1,y)-sum(x,y-1)

It is the same thing as obtaining the sum of a rectangle from (x,y) to (x,y). :S

It should be possible...
But did you started from 0 or from1 in BIT you should always start from 1...

@Mister:

Look at
http://www.z-trening.com/new/www/html/submit.php?submit=7100051261&subm_code=1

This is your code, just defined int bit[1030][1030] ..., and this also works. Why, I don't know.

Can someone help me?
It won't pass 7th, 8th and 9th test case.

http://z-trening.com/submit.php?submit=7100333153&subm_code=1

Testiraj se na primeru:
4
SET 0 0 1
SUM 0 0 3 3
SET 0 0 5
SUM 0 0 3 3
END

Shvatio sam gdje je greska...Hvala!! Samo, sad nemam ideju kako da ispravim..

E sada, ti kada trebaš da promeniš neku vrednost prvo uradiš update za - prava vrednost tog polja a to je suma "pravougaonika" sa temenima (X, Y) i (X, Y) i onda tek vršiš update za tu vrednost. Ok?

Evo dela koda

        if ( Command[1] == 'E' )
        {
            int X, Y, Val;
 
            scanf ( "%d %d %d", &X, &Y, &Val );
 
            X++;
            Y++;
 
            Update ( X, Y, Val - Query ( X, Y, X, Y ) );
 
            continue;
        }
 
        if ( Command[1] == 'U' )
        {
            int X1, Y1, X2, Y2;
 
            scanf ( "%d %d %d %d", &X1, &Y1, &X2, &Y2 );
 
            X1++;
            Y1++;
            X2++;
            Y2++;
 
            printf ( "%d\n", Query ( X1, Y1, X2, Y2 ) );
        }

Hvala !! Tako sam i mislio da treba samo sto prvi put nisam dobro kodirao.. Hvala jos jednom..

I postoji slican zadatak z-product tj u sustini isti sam umjesto sume trazi se proizvod brojeva u odgovarajucem pravougaoniku. Da li tu mogu da se koriste kumulativne tabele?

Da, mogu. Samo pazi kako ćeš da deliš jer

 ( a / b ) % m != ( ( a % m ) / ( b % m ) ) % m