In Search for a better Algorithm

[weidongtom]

Hi,

I was working on the following problem and I managed to get a
solution, but it's too slow. And I am still in search for a better
algorithm. Please enlighten me.

--------------------------------------------------------------------------------------------
Here's my solution
#include <stdio.h>

int array[200][200][200] = {0};

int main(){
int n;
char c;
if(scanf("%d\n", &n) != 1)
return 1;
while(1){
int sum = 0;
int x = 0, y = 0, z = 0, x2 = 0, y2 = 0, z2 =0, i, j, k,
num=0;
if(scanf("%c", &c) == EOF)
break;
switch(c){
case 'A':
if(scanf("%d %d %d %d\n", &x, &y, &z, &num) !=
4)
return 1;
array[x-1][y-1][z-1] += num;
break;
case 'S':
if(scanf("%d %d %d %d\n", &x, &y, &z, &num) !=
4)
return 1;
array[x-1][y-1][z-1] -= num;
break;
case 'Q':
if(scanf("%d %d %d %d %d %d\n", &x, &y, &z,
&x2, &y2, &z2) != 6)
return 1;

for(i = x; i < x2+1; i++){
for(j = y; j < y2+1; j++){
for(k = z; k < z2+1; k++){
sum+=array[i-1][j-1][k-1];
}
}
}
printf("%d\n", sum);
break;
default:
goto end;
break;
}
}
end:
return 0;
}

--------------------------------------------------------------------------------------------
This is the question

Prince Ray wants to marry his girl friend, beautiful Princess Amy. Amy
loves Ray, and is very willing to take him. However, Amy's father,
King StreamSpeed, insists that his son in law should be talented
enough, so that he could let him be the King of this country after
King StreamSpeed retired. So he gives Ray a Test.
Ray is given a large brick of size n*n*n, which contains n*n*n grids
of size 1. Every grid can be represent as a triple(x, y, z) (1<=x, y,
z<=n). There are numbers in every grid. All the numbers are initially
set to zero.
King StreamSpeed will do three operations to the brick.
1. Add a number to a given grid's number
2. Subtract a number from a given grid's number
3. Query the sum of total number from(x1,y1,z1) to (x2,y2,z2)
(x1 <= x2, y1 <= y2, z1 <= z2)
As Ray 's best friend and most excellent coder, you are required to
write a program to answer all the queries to help Ray marry with her
valentine.

ÊäÈë

The first line of the input contains an integer n(1<=n<=100), the size
of the brick. Then follow several lines in the following format:
A x y z num : Add num to (x, y, z)
S x y z num: Subtract num from (x, y, z)
Q x1 y1 z1 x2 y2 z2 : Query the sum of numbers from (x1, y1 , z1) to
(x2 , y2 , z2)
The number of all the queries will be no more than 1000000.Input file
is ended by a zero and should not be processed.



Êä³ö

For every query in the input file, your program should output the
corresponding result -- the sum of numbers in the range (x1, y1, z1)
~(x2, y2, z2). The result does not exceed 10^9.

ÑùÀýÊäÈë

10
A 1 1 4 5
A 2 5 4 5
Q 1 1 1 10 10 10
S 3 4 5 34
Q 1 1 1 10 10 10
0

ÑùÀýÊä³ö

10
-24

Ìáʾ

Huge input file, scanf is recommended.

 

[CBFalconer]

I was working on the following problem and I managed to get a
solution, but it's too slow. And I am still in search for a
better algorithm. Please enlighten me.

----------------------------------------------------------------
Here's my solution
#include <stdio.h>

int array[200][200][200] = {0};

That array has 8,000,000 elements, and even if they are just 1 char
elements you will have a tough time finding a machine with enough
memory to implement it. That means it will always have to be in
virtual memory, and involve disk transfers.

You can probably get away with an array of 40,000 pointers to 200
unit arrays. There you can avoid the storage entirely by
representing empty arrays with a NULL pointer.

Please do not exceed 72 char line length. 67 is better.

 

[Richard Harter]

Hi,

[snip statement and code]

You have posted this before in comp.lang.c. This is the wrong
newsgroup - try comp.programming. You received useful
information in the responses to your original post that you seem
to have ignored. Try posting to an appropriate newsgroup; when
you do read the responses to your post.


Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
But the rhetoric of holistic harmony can generate into a kind of
dotty, Prince Charles-style mysticism. -- Richard Dawkins

 

[weidongtom]

Hi,

[snip statement and code]

You have posted this before in comp.lang.c. This is the wrong
newsgroup - try comp.programming. You received useful
information in the responses to your original post that you seem
to have ignored. Try posting to an appropriate newsgroup; when
you do read the responses to your post.

Richard Harter, [email protected]://home.tiac.net/~cri,http://www.varinoma.com
But the rhetoric of holistic harmony can generate into a kind of
dotty, Prince Charles-style mysticism. -- Richard Dawkins

thanks

 

[jacob navia]

I was working on the following problem and I managed to get a
solution, but it's too slow. And I am still in search for a
better algorithm. Please enlighten me.

----------------------------------------------------------------
Here's my solution
#include <stdio.h>

int array[200][200][200] = {0};

That array has 8,000,000 elements, and even if they are just 1 char
elements you will have a tough time finding a machine with enough
memory to implement it. That means it will always have to be in
virtual memory, and involve disk transfers.

Please Chuck...

I have 2GB RAM installed, and at work I have routinely
4GB machines!

An array of 8MB is quite small this days. Yes, I know this
is inflation, but it is the way everything goes.

But maybe you are still using your famous 486?
In that case, 8MB is a lot of course.

You can probably get away with an array of 40,000 pointers to 200
unit arrays. There you can avoid the storage entirely by
representing empty arrays with a NULL pointer.

Please do not exceed 72 char line length. 67 is better.

Same thing. Screens of 1900x1200 pixels are common this days,
and I can't even buy a screen with less than 1280x1024. Why
72 chars line length?

Your post gives the impression to the (possible) younger
people that we are a hopelessly backward bunch of old guys
living somewhere in the 80s.

jacob

 

[Ian Collins]

Same thing. Screens of 1900x1200 pixels are common this days,
and I can't even buy a screen with less than 1280x1024. Why
72 chars line length?

Now come on Jacob, you've been here long enough to know that the
regulars here still read Usenet on their Teletypes or Wise terminals
over a 110 baud, 19" modem.

 

[Chris Torek]

[OT drift, probably should not post this at all, but it is late ]

... you've been here long enough to know that the
regulars here still read Usenet on their Teletypes or Wise terminals
over a 110 baud, 19" modem.

That's "Wyse", not "Wise". I prefer my H19 though. Wyse magic
cookies, ugh.

(Actually, my H19 died years ago. Built it in the mid-1980s ...
a few years later, the decode chip for the keyboard got squirrelly,
but I found that a pullup resistor on one of the pins would make
it reliable. Kept the thing going until the mid-1990s or so.
Also, the first modem I personally owned was a Telebit Trailblazer.
I did have to use 110 baud for a while, though, as the 300 baud
mode on the acoustic coupler built in to the Silent 700 I had
borrowed suffered from too much noise.)

(Also, there was at least one Wyse that did not suffer so badly
from the "magic cookie" problem. I forget which model, but
Pyramid liked to use it as their console display. The U of MD
had one of the early wire-wrapped Pyramid machines.)

 

[Christopher Benson-Manica]

int array[200][200][200] = {0};

That array has 8,000,000 elements, and even if they are just 1 char
elements you will have a tough time finding a machine with enough
memory to implement it.

As Jacob noted, that's sizeof(int)*8,000,000 bytes; we all have
machines that can handle that if they're so inclined. Whether there
is that much automatic storage available is another question (as we
all know). Perhaps that's what you meant to refer to.

You can probably get away with an array of 40,000 pointers to 200
unit arrays. There you can avoid the storage entirely by
representing empty arrays with a NULL pointer.

An array of 200 int**'s would eliminate the "probably", but I did not
see the original post, so I couldn't say whether that would be
helpful.

Please do not exceed 72 char line length. 67 is better.

67 sounds a little overzealous to me; the line length here is 70.

 

[Richard]

int array[200][200][200] = {0};

That array has 8,000,000 elements, and even if they are just 1 char
elements you will have a tough time finding a machine with enough
memory to implement it.

As Jacob noted, that's sizeof(int)*8,000,000 bytes; we all have
machines that can handle that if they're so inclined. Whether there
is that much automatic storage available is another question (as we
all know). Perhaps that's what you meant to refer to.

You can probably get away with an array of 40,000 pointers to 200
unit arrays. There you can avoid the storage entirely by
representing empty arrays with a NULL pointer.

An array of 200 int**'s would eliminate the "probably", but I did not
see the original post, so I couldn't say whether that would be
helpful.

Please do not exceed 72 char line length. 67 is better.

67 sounds a little overzealous to me; the line length here is 70.

Please pay no attention to Falconer. Until he learns to post with one
signature that is.

 

[osmium]

I was working on the following problem and I managed to get a
solution, but it's too slow. And I am still in search for a better
algorithm. Please enlighten me.

--------------------------------------------------------------------------------------------
Here's my solution
#include <stdio.h>

int array[200][200][200] = {0};

Look up sparse arrays on the Web. I really detest the way your instructor
worded that problem. Maybe it is a cultural thing ....

<snip>

 

[Charlie Gordon]

int array[200][200][200] = {0};

That array has 8,000,000 elements, and even if they are just 1 char
elements you will have a tough time finding a machine with enough
memory to implement it. That means it will always have to be in
virtual memory, and involve disk transfers.

Unless the OP is programming on very old hardware, a 32MB array should not
be concern.
Furthermore, the OP knows the value of n is in the range 1 <= n <= 100. Why
not test that in the program and reduce the array to ``int
array[100][100][100]'' ?

It might also be more efficient to use powers of 2 for the array dimensions,
such as ``int array[128][128][128]'' but the potential gains on address
calculations may be lost to cache collisions.

Test these propositions, ans see if it helps speed up the program.

You can probably get away with an array of 40,000 pointers to 200
unit arrays. There you can avoid the storage entirely by
representing empty arrays with a NULL pointer.

I'm afraid that would lead to an even slower program, defeating the OPs
goal.

Please do not exceed 72 char line length. 67 is better.

For posting on Usenet, short lines are better indeed, but I would not limit
program lines to 67 in actual program sources.