Optimization Problem

[weidongtom]

Hi,

I was submitting a solution of a certain problem to the online judge,
but it says my program is exceeding the time limit, I've been doing
some tweaks to my codes but still it didn't get me through, so please
help me out here. Thanks in advance.

/* Input:
A x y z num {to add num to array[x][y][z]}
or
S x y z num {to sub num from array[x][y][z]
or
Q x1 y1 z1 x2 y2 z2 {where x1<= xi <= x2, y1<= yi <= y2, z1<= zi <=
z2, find the sums of all the values xi, yi, zi}
*/

#include <stdio.h>
#include <stdlib.h>

int array[300*300*300]={0};

int main(){
int n, x1, y1, z1, x2, y2, z2, num, total = 0, n_square;
char action;
scanf("%d\n", &n);
n_square= n*n;

while(1){
int sum = 0;
if(scanf("%c", &action) == EOF)
return 1;
switch(action){
case '0':
return 0;
case 'A':
scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);
array[(x1-1)+(y1-1)*n+(z1-1)*n_square] += num;
total += num;
break;
case 'S':
scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);
array[(x1-1)+(y1-1)*n+(z1-1)*n_square] -= num;
total -= num;
break;
case 'Q':
scanf("%d %d %d %d %d %d\n", &x1, &y1, &z1,
&x2, &y2, &z2);
if(x1 == 0 && x2 == n && y1 == 0 && y2 == n &&
z1 == 0 && z2 == n)
printf("%d\n", total);
else{
int i, j , k;
for(i = x1; i < x2+1; i++){
for(j = y1; j < y2+1; j++){
for(k = z1; k < z2+1; k++){
sum += array[(i-1)+(j-1)*n+
(k-1)*n_square];
}
}
}
printf("%d\n", sum);
}
break;
default:
return 1;
}
}
return 0;
}

 

[user923005]

To find out where the time is going with your program, use a profiler.
The GNU gprof profiler is free.

 

[Richard Heathfield]

user923005 said:

To find out where the time is going with your program, use a profiler.
The GNU gprof profiler is free.

Context is always useful.

 

[Willem]

(e-mail address removed) wrote:
) I was submitting a solution of a certain problem to the online judge,
) but it says my program is exceeding the time limit, I've been doing
) some tweaks to my codes but still it didn't get me through, so please
) help me out here. Thanks in advance.

You can't know what will increase the speed of your program without
testing, but there's something about your code that tends to be very
sub-optimal on most modern computers:

) <snip>
) int i, j , k;
) for(i = x1; i < x2+1; i++){
) for(j = y1; j < y2+1; j++){
) for(k = z1; k < z2+1; k++){
) sum += array[(i-1)+(j-1)*n+
) (k-1)*n_square];
) }
) }
) }
) printf("%d\n", sum);
) <snip>

The memory on most modern PCs is such that when you read it in order,
it goes a lot faster. So when you access a lot of elements of an array,
try to do it so that you read element X+1 after reading element X.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Ben Bacarisse]

I was submitting a solution of a certain problem to the online judge,
but it says my program is exceeding the time limit, I've been doing
some tweaks to my codes but still it didn't get me through, so please
help me out here. Thanks in advance.

scanf("%d\n", &n);

if(scanf("%c", &action) == EOF)

scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);

scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);

scanf("%d %d %d %d %d %d\n", &x1, &y1, &z1,
&x2, &y2, &z2);

You should (almost) always test the result for scanf. When you do
test the result, it is almost always better to test for success (== 1,
== 4, etc) rather than for one type of failure (== EOF).

 

[user923005]

user923005 said:


Context is always useful.

The title together with the statements is all that is needed in this
follow-up.
Nothing additional will be gained by stating (for instance) the
particulars about the problem.
IMO-YMMV.

 

[CBFalconer]

The title together with the statements is all that is needed in
this follow-up. Nothing additional will be gained by stating
(for instance) the particulars about the problem. IMO-YMMV.

You don't realize the situation, especially using the google
interface to Usenet. Usenet is a best efforts delivery
philosophy. There is no guarantee that any other reader of your
post has ever, or ever will, be able to read any other posts in the
thread. This makes it essential to quote sufficient material in
each reply so that that reply stands by itself.

Even the google interface is capable of doing this, judging by
other posters.

 

[Richard Heathfield]

CBFalconer said:

You don't realize the situation, especially using the google
interface to Usenet.

I doubt that very much; user923005 has been around the block a few times,
and he knows exactly how Usenet works. He's just being ornery. The only
cure for his intransigence is the edge of Dann Corbit's poleaxe.

<snip>

 

[Barry Schwarz]

Hi,

I was submitting a solution of a certain problem to the online judge,
but it says my program is exceeding the time limit, I've been doing
some tweaks to my codes but still it didn't get me through, so please
help me out here. Thanks in advance.

/* Input:
A x y z num {to add num to array[x][y][z]}
or
S x y z num {to sub num from array[x][y][z]
or
Q x1 y1 z1 x2 y2 z2 {where x1<= xi <= x2, y1<= yi <= y2, z1<= zi <=
z2, find the sums of all the values xi, yi, zi}
*/

#include <stdio.h>
#include <stdlib.h>

Do you use anything declared in stdlib.h?

int array[300*300*300]={0};

If the requirement is to deal with up to 300 elements in each
dimension, make the array 301*301*301.

By using a 1D array to simulate a 3D array, you eliminate any help the
compiler can give you in terms of optimizing array access. You do not
gain a single byte of space.

int main(){
int n, x1, y1, z1, x2, y2, z2, num, total = 0, n_square;
char action;
scanf("%d\n", &n);

You should test that n is between 1 and whatever the maximum dimension
is.

n_square= n*n;

while(1){
int sum = 0;
if(scanf("%c", &action) == EOF)
return 1;

This is a non-portable return value from main. Furthermore, you
should not be exiting the program at this point. You should only be
exiting the while loop.

switch(action){
case '0':
return 0;

This is a portable return value but still not the time to be exiting
main.

case 'A':
scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);

You should check the return value from scanf to insure you received
all four values.

I assume the online judge is redirecting stdin to a file. scanf is a
pretty complex function. I wonder if it would be faster to use fgets
followed by a series of calls to strtol.

array[(x1-1)+(y1-1)*n+(z1-1)*n_square] += num;

Eliminate the -1 terms in all the expressions. You might want to make
the array element expression a macro to save typing.

total += num;

While you are debugging your code, add something like

printf("Case A: x=%d, y=%d, z=%d, num=%d, array=%d,
total=%d\n", x1, y1, z1, num, array[...], total);

break;
case 'S':
scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);
array[(x1-1)+(y1-1)*n+(z1-1)*n_square] -= num;
total -= num;

Same two comments apply.

break;
case 'Q':
scanf("%d %d %d %d %d %d\n", &x1, &y1, &z1,
&x2, &y2, &z2);

Check to make sure scanf found all six inputs.

if(x1 == 0 && x2 == n && y1 == 0 && y2 == n &&
z1 == 0 && z2 == n)

0 should never be a valid input. All six inputs should be range
checked.

printf("%d\n", total);
else{

A good place for some more debugging output.

int i, j , k;
for(i = x1; i < x2+1; i++){
for(j = y1; j < y2+1; j++){
for(k = z1; k < z2+1; k++){
sum += array[(i-1)+(j-1)*n+
(k-1)*n_square];
}
}
}
printf("%d\n", sum);
}

Here also.

break;
default:
return 1;

Do you really want to quit the program here? Do you even want to quit
the while loop because of an unexpected input?

}
}
return 0;

Your only way out of the while loop is via the return statements. This
statement can never execute. The return statements in the while
should be break statements so you get here. Before returning from
main, you should print some end of job message.

}

Remove del for email

 

[CBFalconer]

I was submitting a solution of a certain problem to the online
judge, but it says my program is exceeding the time limit, I've
been doing some tweaks to my codes but still it didn't get me
through, so please help me out here. Thanks in advance.

Maybe the time limit is on when to submit entries?

 

[Richard Harter]

Hi,

I was submitting a solution of a certain problem to the online judge,
but it says my program is exceeding the time limit, I've been doing
some tweaks to my codes but still it didn't get me through, so please
help me out here. Thanks in advance.

[snip code]

You have had several execellent responses commenting on your C
code; learn from them. However your problem is not a C problem;
it is a programming problem.
<OT>
The essence of the problem is that you have a large sparse array
in which almost all entries are zero. You alter entries in an
interactive loop. Upon demand you print out the sum of all
entries within a subarray.

The programming issue is that the cost of looping through the
entire array is enormous whereas the cost of looping through the
actual number of non-zero entries is small, that being no more
than the number of interactive entries.

The point of the problem is to devise a choose a data structure
and algorithm for which the cost is proportional to the actual
size of the non-zero data.

Repost in comp.programming if you want suggestions about doing
that.
</OT>

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