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.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Ben Bacarisse]

"we********@gmail.com" <we********@gmail.comwrites:

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).

--
Ben.

[Barry Schwarz]

On Tue, 25 Sep 2007 05:38:45 -0700, "we********@gmail.com"
<we********@gmail.comwrote:

>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]

"we********@gmail.com" 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.

Maybe the time limit is on when to submit entries?

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

[Richard Harter]

On Tue, 25 Sep 2007 05:38:45 -0700, "we********@gmail.com"
<we********@gmail.comwrote:

>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, cr*@tiac.net
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