100 - The 3n + 1 problem

[226]

the problem 100 has so easy a solution that the judge has even put up as an example.
yet there are people who have submitted that problem in less than
25 ms.can anybody suggest better algorihtms than the simple brute force and the idea of memoization(using an array of 1000000 elements)

[newhh2002]

i use LCC-win32, the program can run, but why i get ce now? thanks

//3n+1

#include <stdio.h>

#define MAXNUM 60000 //cache

int table[MAXNUM];

int GetCount(unsigned long int n)
{
unsigned long int nn;
int result;
if (n<=MAXNUM && table[n-1]!=0)
return table[n-1];
if (n&1)
nn=n*3+1;
else
nn=n>>1;
result=1+GetCount(nn);
if (n<=MAXNUM)
table[n-1]=result;
return result;
}

void main()
{
int start,end;
int i;
int maxCount,thisCount;
for (i=1;i<MAXNUM;i++)
table=0;
table[0]=1;
while (1)
{
maxCount=0;
scanf("%d %d",&start,&end);
if (start==0 && end==0)
break;
for (i=start;i<=end;i++)
{
thisCount=GetCount(i);
if (thisCount>maxCount)
maxCount=thisCount;
}
printf("%d %d %d\n",start,end,maxCount);
}
}

[newhh2002]

could someone help me with #100? i've almost give up. i tested with many special cases but finally it does not pass

the following program results in "time limit exceed"(as you can see, i even added some "constants" in the program, so the speed should be fast). if i remove "table[maxnum]" and the "constants", it still results in "tle", however, if i change
scanf("%d %d",&start,&end);
in main() into
if (scanf("%d %d",&start,&end)!=2) break;
it results in "wrong answer"
could someone help me? thank you very much!!!!!!!!

(code see below... )

[Larry]

just a note: start doesn't have to be bigger than end.

and please do a search on the forum before asking.. there are a few ways to optimize this problem..

[epsilon0]

programming guidelines:

no function longer than ten lines
clean identation

try it out!

in case your program was properly indented, use the C function of this board to post it so people can read it!

example:

[c]int main(int argc, char **argv)
{
init();
solve();
clean();
return EXIT_SUCCESS;
}
[/c]

[epsilon0]

the problem 100 is very fallacious.

my program was accepted, yet it did not work.

explanation:

some of the intermediate results are greater than 2^32 thus using the C type "unsigned int" or any equivalent is WRONG.

this could lead to wrong results if the judge had chosed the input test data in a vicious (yet fair) way.

i really hope the judge changes the input data of this problem, so my program becomes WA, because it's all it deserves.

[newhh2002]

just a note: start doesn't have to be bigger than end.

and please do a search on the forum before asking.. there are a few ways to optimize this problem..

i tried but still tle
i tried on my pentium 133, speed is not the problem because i used "constants" and "cache", but i can't pass the judge:``(

[newhh2002]

programming guidelines:

no function longer than ten lines
clean identation

try it out!

in case your program was properly indented, use the C function of this board to post it so people can read it!

example:

[c]int main(int argc, char **argv)
{
init();
solve();
clean();
return EXIT_SUCCESS;
}
[/c]

thank you for your advice, i'll post it again
no function longer than ten lines.... well, i first thought #100 is a simple problem so i just decided to use main() and GetCount() (getcount() is a recursion function and i don't want main() to be recursive), i thought the fewer functions, the better. however, i added some "constants" to improve speed, so main() become bigger anyhow, thank you very much!

[newhh2002]

[c]
//3n+1
#include <stdio.h>

#define MAXNUM 30000

int table[MAXNUM]; //for "cache" use, no need too big

int GetCount(long long n)
{
long long nn;
int result;
if (n<=MAXNUM && table[n-1]!=0) //result is found in "cache"
return table[n-1];
if (n&1)
nn=n*3+1;
else
nn=n>>1;
result=1+GetCount(nn);
if (n<=MAXNUM)
table[n-1]=result; //save to "cache"
return result;
}

void main()
{
int start,end;
int i;
int maxCount,thisCount;
for (i=1;i<MAXNUM;i++) //init cache
table=0;
table[0]=1; //end of init cache
while (1)
{
maxCount=0; //the result of a case is saved here, and is initialized to zero
scanf("%d %d",&start,&end); //wrong here? as mentioned at top
if (start==0 && end==0)
break; //according to "rule"
//start maybe bigger than end, so swap
if (start>end)
{
i=end;
end=start;
start=i;
}
//the following lines are "constants"
if (start<=837799 && end>=837799)
{
printf("%d %d %d\n",start,end,525);
continue;
}
if (start<=626331 && end>=626331)
{
printf("%d %d %d\n",start,end,509);
continue;
}
if (end<626331 && start<=511935 && end>=511935)
{
printf("%d %d %d\n",start,end,470);
continue;
}
if (end<511935 && start<=410011 && end>=410011)
{
printf("%d %d %d\n",start,end,449);
continue;
}
if (end<410011 && start<=230631 && end>=230631)
{
printf("%d %d %d\n",start,end,443);
continue;
} //end of "constants"
for (i=end;i>=start;i--)
{
thisCount=GetCount((long long)i);
if (thisCount>maxCount)
maxCount=thisCount;
}
printf("%d %d %d\n",start,end,maxCount);
}
}
[/c]
thanks for reading!!!!

[newhh2002]

finally i know! it's multiple input :`(
but why still WA?
[c]
//3n+1
#include <stdio.h>
#include <string.h>

#define MAXNUM 60000

int table[MAXNUM];

int GetCount(long long n)
{
long long nn;
int result;
if (n<=MAXNUM && table[n-1]!=0)
return table[n-1];
if (n&1)
nn=n*3+1;
else
nn=n>>1;
result=1+GetCount(nn);
if (n<=MAXNUM)
table[n-1]=result;
return result;
}

void main()
{
int start,end;
int i,pc,newp;
int maxCount,thisCount;
char line[20];
for (i=1;i<MAXNUM;i++)
table=0;
table[0]=1;
scanf("%d",&pc);
gets(line);
gets(line);
newp=0;
while (1)
{
maxCount=0;
if (gets(line))
{
if (strlen(line)==0 || sscanf(line,"%d %d",&start,&end)!=2)
{
newp=1;
continue;
}
}
else
break;
if (newp)
{
printf("\n");
newp=0;
}
if (start>end)
{
i=end;
end=start;
start=i;
}
if (start<=837799 && end>=837799)
{
printf("%d %d %d\n",start,end,525);
continue;
}
if (start<=626331 && end>=626331)
{
printf("%d %d %d\n",start,end,509);
continue;
}
if (end<626331 && start<=511935 && end>=511935)
{
printf("%d %d %d\n",start,end,470);
continue;
}
if (end<511935 && start<=410011 && end>=410011)
{
printf("%d %d %d\n",start,end,449);
continue;
}
if (end<410011 && start<=230631 && end>=230631)
{
printf("%d %d %d\n",start,end,443);
continue;
}
for (i=end;i>=start;i--)
{
thisCount=GetCount((long long)i);
if (thisCount>maxCount)
maxCount=thisCount;
}
printf("%d %d %d\n",start,end,maxCount);
}
}

[/c]

[Eric____]

can some body point me to the rite directn
it works fine on my machine, for the sample cases

error:
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.027 seconds.

C++:

#include <iostream.h>

int arr[1000001] ;

int get(int d)
{
if (arr[d]!=0)
return arr[d];
else
if (d%2==0)
{ arr[d] = get(d/2)+1;
return arr[d];
}
else
{ arr[d] = get(3*d+1)+1;
return arr[d];
}

}

void main ()
{ int a, b;

int i;

int largest;
for (i=0; i<1000001; i++)
arr = 0;
arr[1]=1;
arr[2] =2;

while (cin>>a>>b)
{ if (a>b) break;
largest = get(a);
for (i=a; i<=b; i++)
{ if (get(i)>largest)
largest = get(i);
}
cout <<a<<" "<<b<<" "<<largest<<endl;
}
}

[Eric____]

thanks for reply
but same result.

[Eric____]

i got it now, probably judge doesnt like my array

[Smeagol '_']

hi guys, i know you get a lot of postings on problem 100 ... but i've tried everything on this problem and i still get a wrong answer!!! : ( and lots of memory used, i know is because of the array but... Can anybody take a look at it and help me a little bit
[cpp]

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int main()
{
register unsigned int first =0;
register unsigned int last =0;
int* array = new int[1000000];

while(scanf("%d %d",&first, &last)==2)
{

register int count=1;
register int max=1;

if(first > last)
{
register unsigned int tmp=first;
first=last;
last=tmp;
}
for(register unsigned int i=first;i<=last;i++)
{
if(array == 0)
{
register unsigned int k=i;
count=1;
while(k!=1)
{
if(k%2 != 0) k=(3*k)+1;
else k/=2;
count++;
}
array=count;
}
else
count=array;

if(max<count)
max=count;
}
printf(" %d\n",max);

char c=getchar();
ungetc(c,stdin);
if(c=='\n')
printf("\n");

}

return 0;
}

[/cpp]

[Smeagol '_']

ok forget it , my bad!! LOL