Velocity Reviews > Optimization Problem

# Optimization Problem

weidongtom@gmail.com
Guest
Posts: n/a

 09-25-2007
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
Guest
Posts: n/a

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

Richard Heathfield
Guest
Posts: n/a

 09-25-2007
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

Willem
Guest
Posts: n/a

 09-25-2007
http://www.velocityreviews.com/forums/(E-Mail 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
Guest
Posts: n/a

 09-25-2007
"(E-Mail Removed)" <(E-Mail Removed)> 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.

user923005
Guest
Posts: n/a

 09-26-2007
On Sep 25, 11:55 am, Richard Heathfield <(E-Mail Removed)> 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.

CBFalconer
Guest
Posts: n/a

 09-26-2007
user923005 wrote:
> Richard Heathfield <(E-Mail Removed)> 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

Richard Heathfield
Guest
Posts: n/a

 09-26-2007
CBFalconer said:

> user923005 wrote:
>> Richard Heathfield <(E-Mail Removed)> 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

Barry Schwarz
Guest
Posts: n/a

 09-26-2007
On Tue, 25 Sep 2007 05:38:45 -0700, "(E-Mail Removed)"
<(E-Mail Removed)> 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

CBFalconer
Guest
Posts: n/a

 09-26-2007
"(E-Mail 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

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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Ravikiran C Programming 22 11-24-2008 03:19 AM ashu VHDL 5 05-16-2006 03:48 PM DENG Python 6 09-02-2005 01:16 PM JE C++ 2 08-05-2004 08:22 AM JE Perl 0 08-04-2004 06:52 PM