# Optimization Problem

Discussion in 'C Programming' started by weidongtom@gmail.com, Sep 25, 2007.

1. ### Guest

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;
}

, Sep 25, 2007

2. ### user923005Guest

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

user923005, Sep 25, 2007

3. ### Richard HeathfieldGuest

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@
"Usenet is a strange place" - dmr 29 July 1999

Richard Heathfield, Sep 25, 2007
4. ### WillemGuest

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

Willem, Sep 25, 2007
5. ### Ben BacarisseGuest

"" <> writes:

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

Ben Bacarisse, Sep 25, 2007
6. ### user923005Guest

On Sep 25, 11:55 am, Richard Heathfield <> wrote:
> 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.

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
IMO-YMMV.

user923005, Sep 26, 2007
7. ### CBFalconerGuest

user923005 wrote:
> Richard Heathfield <> wrote:
>> 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.

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

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

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

CBFalconer, Sep 26, 2007
8. ### Richard HeathfieldGuest

CBFalconer said:

> user923005 wrote:
>> Richard Heathfield <> wrote:
>>> 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.

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

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>

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

Richard Heathfield, Sep 26, 2007
9. ### Barry SchwarzGuest

On Tue, 25 Sep 2007 05:38:45 -0700, ""
<> wrote:

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

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;

> 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

Barry Schwarz, Sep 26, 2007
10. ### CBFalconerGuest

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

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

CBFalconer, Sep 26, 2007
11. ### Richard HarterGuest

On Tue, 25 Sep 2007 05:38:45 -0700, ""
<> wrote:

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

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

Richard Harter, Sep 26, 2007