100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

226
New poster
Posts: 1
Joined: Wed Jan 22, 2003 5:09 pm

simple yet deceptive

Post by 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)
every problem has a short,sweet solution
that is just a bit far away.

newhh2002
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

#100 why compile error or time limit? :(

Post by 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);
}
}
none

newhh2002
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

HELP 100 :..( wa/tle

Post by 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... :P)
Last edited by newhh2002 on Mon Jan 27, 2003 5:28 pm, edited 1 time in total.
none

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by 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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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]
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

newhh2002
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

Post by newhh2002 »

Larry wrote: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:``(
none

newhh2002
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

Post by newhh2002 »

epsilon0 wrote: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!
none

newhh2002
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

Post by 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!!!!
none

newhh2002
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

Post by 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]
none

Eric____
New poster
Posts: 8
Joined: Thu Jan 30, 2003 10:13 am
Contact:

100, runtime error

Post by 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____
New poster
Posts: 8
Joined: Thu Jan 30, 2003 10:13 am
Contact:

Post by Eric____ »

thanks for reply
but same result. :(

Eric____
New poster
Posts: 8
Joined: Thu Jan 30, 2003 10:13 am
Contact:

Post by Eric____ »

i got it now, probably judge doesnt like my array

Smeagol '_'
New poster
Posts: 10
Joined: Tue Feb 04, 2003 11:38 pm

Wrong Answer on p100 '_'

Post by 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 :D
[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 '_'
New poster
Posts: 10
Joined: Tue Feb 04, 2003 11:38 pm

Post by Smeagol '_' »

ok forget it , my bad!! LOL :D

Post Reply

Return to “Volume 1 (100-199)”