371 - Ackermann Functions

[MAXX^FACTOR]

Maybe you can replace '/2' and '%2' with shift operator '>>' for higher
efficiency.

[Eric]

Finally, I solved the problem.
Thanks all of you.

[epsilon0]

goto???? <---- /* OH! */

also... i doubt it can make it much faster, but:

1] you compute cycle(i) twice. your for loop should start at i+1.

2] the 2nd if (InpI >InpJ) test is useless.

the rest seems perfect. if you removed the mysterious GOTO, it would most likely get accepted?

[Larry]

You can cache some results.

Also, you can probably optimized a thing or two here, since the first time I got AC, I don't think I cache anything, so you just have to be careful, like:

Code: Select all

while(m!=1){
if((m%2)==0) m/=2; else m=(3*m)+1;
n++;
}

can be converted to:

Code: Select all

while(m!=1){
if((m%2)==0) m/=2; else m=((3*m)+1)/2;
n++;
}

[/code]

[abyssinian]

err.....need help...i think that i have made all possible adjustment ..
but i still get the over limit (10.47 seconds..)....confused where's wrong..??
can anybody give me a hint??



#include<stdio.h>

int main(){
long int l,u,i,x,max,y,z;
int sequence[1000];

while(scanf("%li %li",&l,&u)==2){
max=0;
if(l==0 && u==0) break;

for(i=l;i<=u;++i){
sequence=0;
x=i;
do{
if (x&1) {x=3*x+1;
}else {x=x>>1;}
++sequence;
}while(x!=1);

if(sequence>max) {max=sequence;y=i;}
}

printf("Between %li and %li, %li generates the longest sequence of %li values.",l,u,y,max);
}

return 0;
}

[tat tvam asi]

helo
precomputation ...
bye

[abyssinian]

...emm...precomputation...??
sorry...i don't quite understand....
can you explain it more details plz??.......

[tat tvam asi]

helo
think of input like:
1 100
1 101
1 102
1 103
1 1000
1 2000
...
computing the cycle length
more than once leads to
inefficiency . you need a
big array ( say size of 100000 ) ,
fill it up with the
cycle lengths . use brute force or
be careful and try to use that
cyc. len ( 2 * n ) =
1 + cyc. len. ( n )
and
1 + cyc. len. ( 3 * n + 1 ) =
cyc. len. ( n )
bye

[rjhadley]

Try using unsigned long's: http://acm.uva.es/board/viewtopic.php?t=771.

[abyssinian]

emm..i see your point..
then i try to change my program as follow....
but i got runtime error : invalid memory reference...
is it because of the size of array isn't enough or something else??



#include<stdio.h>

int main(){
long int l,u,i,x,max,y,angka;
int sequence[100000];

for(i=0;i<100000;++i){sequence=0;}

#ifndef ONLINE_JUDGE
freopen("371.in", "r", stdin);
freopen("371.out", "w", stdout);
#endif


while(scanf("%li %li",&l,&u)==2){


max=0;
if(l==0 && u==0) break;

for(i=l;i<=u;++i){
if(sequence==0){
angka=x=i;
do{
if (x&1) {x=3*x+1;
}else {x=x>>1;}
++sequence;
if(x<angka && x>=l) {sequence+=sequence[x];break;}
}while(x!=1);
}

if(sequence>max) {max=sequence;y=i;}
}

printf("Between %li and %li, %li generates the longest sequence of %li values.",l,u,y,max);
}

return 0;
}

[tat tvam asi]

helo
please fill up the
array 'sequence' before
the processing of input ...
... if you need the cycle
length of a number >= 100000
then begin to generate the
sequence until you reach a
number < 100000 . then
cyclen of this num +
num of steps is ...
bye

[abyssinian]

i made some changes....now i got time lim,it exceeded 10,031 second..
are there any possibility i can speed up my program??


#include<stdio.h>

int main(){
long int l,u,i,x,max,y,angka;
int sequence[100000];

#ifndef ONLINE_JUDGE
freopen("371.in", "r", stdin);
freopen("371.out", "w", stdout);
#endif


while(scanf("%li %li",&l,&u)==2){

max=0;
if(l==0 && u==0) break;

for(i=l;i<=u;++i){
sequence=0;
angka=x=i;
do{
if (x&1) {x=3*x+1;
}else {x=x>>1;}
++sequence;
if(x<angka && x>=l) {sequence+=sequence[x];break;}
}while(x!=1);
if(sequence>max) {max=sequence;y=i;}
}

printf("Between %li and %li, %li generates the longest sequence of %li
values.\n",l,u,y,max);
}

return 0;
}

[Sajid]

hi Tanzim,

I've compiled ur code, but I can find bug in ur program.
u didn't think that,

1 1
2 2
...

can be input. you should care about it.


And, u have posted more than 1 New Topic for the same problem. It's not good.

u should also read all the previous posts about the problem, with which u r going to post a topic.

I dont prefer posting the full source code on the board. Try to give up this habbit.
Best of LUCK.

[Jalal]

No sajid he will fell again in TL problem if he made that correct.
The best solution of the prolem is decreasing unimportant works
that he did.
Most person who solved the problem that i know have faced the
TLE at least 3 to 10 times
So, its really tricky one to solve in margin line

[Hisoka]

Tanzim, your algo like mine, but I think your TLE because you use Long int for this problem is not corect, because if the odd number like n= 3212345541 3*n+1 can be larger than 2^32 and produce negative result and this is can make looping forever. you can use double and fmod for this problem.

I wish you can get AC with this.