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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

Hello Brother,
It is not called memorization.

The correct form is MEMOIZATION..
Thank you.
ANUPAM
"Everything should be made simple, but not always simpler"
Farqaleet
New poster
Posts: 15
Joined: Wed Jan 28, 2004 11:24 pm

Strange input problem...

Post by Farqaleet »

Please can anybody tell me why the judge accepts the first one but doesn't accept the second one and gives a time-limit exceeded error. While on my computer with MSVC++ compiler it's exactly the opposite; the first one runs fine while in the second case time is exceeded because the loop doesn't exit with start and end are zero.

[cpp]
int main(int argc, char* argv[])
{
long nStart, nEnd, nMax;

RedNum[1]=1;
while(cin>>nStart>>nEnd)
{
if(nStart<nEnd)
nMax = MaxCycle(nStart, nEnd);
else
nMax = MaxCycle(nEnd, nStart);
cout << nStart << ' ' << nEnd << ' ' << nMax << endl;

}

return 0;
}
[/cpp]


[cpp]
#include <iostream.h>

#define SIZE 1000000

unsigned short MaxCycle(unsigned long Start, unsigned long End);
unsigned short ReduceAlgo(unsigned long n);
unsigned short ReduceAlgo2(unsigned long n);

unsigned short RedNum[SIZE + 1] = {0};


int main(int argc, char* argv[])
{
long nStart, nEnd, nMax;

RedNum[1]=1;
scanf("%d %d", &nStart, &nEnd);

while(nStart!=0 && nEnd!=0)
{
if(nStart<nEnd)
nMax = MaxCycle(nStart, nEnd);
else
nMax = MaxCycle(nEnd, nStart);
printf("%d %d %d\n", nStart, nEnd, nMax);

scanf("%d %d", &nStart, &nEnd);
}

return 0;
}

unsigned short MaxCycle(unsigned long Start, unsigned long End)
{
unsigned short nMax=1, nCur;
for(;Start<=End; Start++)
{
nCur = ReduceAlgo(Start);
if(nCur > nMax)
nMax = nCur;
}

return nMax;
}

/* Recursive */
unsigned short ReduceAlgo(unsigned long n)
{
if(n==1)
return 1;

if(n<SIZE)
{
if(RedNum[n])
return RedNum[n];

if(n%2)
RedNum[n] = ReduceAlgo(3*n + 1) + 1;
else
RedNum[n] = ReduceAlgo(n/2) + 1;

return RedNum[n];
}
else
{
if(n%2)
return ReduceAlgo2(3*n + 1) + 1;
else
return ReduceAlgo2(n/2) + 1;
}
}

/* iterative */
unsigned short ReduceAlgo2(unsigned long n)
{
short ctr=1;

while(n != 1)
{
if(n<SIZE && RedNum[n])
return RedNum[n] + ctr - 1;

if(n%2)
n = 3*n + 1;
else
n = n/2;

ctr++;
}
return ctr;
}[/cpp]
:roll: :( :o [/cpp]
Farqaleet
New poster
Posts: 15
Joined: Wed Jan 28, 2004 11:24 pm

Try this to improve your time

Post by Farqaleet »

I don't know why it takes more time. Remove the condition

[cpp] curNumber > 100 [/cpp]

In a loop of a million, this will take more processing than it will without it.

I have used the same learning technique using recursive decent rather than iterative. It gave me 0.131. see if you can gain some points and help me with my problem. Here it is:

http://online-judge.uva.es/board/viewto ... c&start=45
Farqaleet
New poster
Posts: 15
Joined: Wed Jan 28, 2004 11:24 pm

Post by Farqaleet »

I found out why the first one is accepted by the judge.

The reason is that rather than handling the stdin directly, the judge simply redirects stdin to a file so when we read, it reads from a file. So when the EOF character of the file is encountered, the while loop exits. But EOF = 0 so the second one should also exit but it doesn't. And I still don't know why.
nightdog
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm

Post by nightdog »

in the second one, you don't quit the program unless you have a valid INPUT with the value 0.
the judge doesn't input u that value, it just gives you an EOF.
the solution would be checking for EOF in the return value of scanf, not it's variables.


wrong:
[c]
scanf("%d %d",&i,&j);
while(i != 0 && j != 0)
[/c]
right:
[c]
while(scanf("%d %d",&i,&j) != EOF)
[/c]
Farqaleet
New poster
Posts: 15
Joined: Wed Jan 28, 2004 11:24 pm

Post by Farqaleet »

You are right. I didn't think of that. Thanx for the help. :)

I confused it with another question that did give 0 0 as the ending input.

But I don't think that the second one should work either. The reason is that scanf returns the number of inputs read, not what was read. I haven't tested it but I think it is so. so if scanf reads 0 numbers for the last line and EOF = -1 as given below then it will still continue.

But this definitely does work:
[cpp]
while(scanf("%d %d",&i,&j) != EOF)
[/cpp]

well any ways I found what the problem was. Following is how IOS.h defines some constants

[cpp]
#ifndef NULL
#define NULL 0
#endif

#ifndef EOF
#define EOF (-1)
#endif
[/cpp]

EOF is -1, not 0, which was my mistake. I mistook EOF to be 0;

Thanx alot. :wink:
Farqaleet
New poster
Posts: 15
Joined: Wed Jan 28, 2004 11:24 pm

Post by Farqaleet »

Sorry for the typo above. :lol: Here is what does work
[cpp]
while(scanf("%d %d",&i,&j) != 0)
[/cpp]
39949FP
New poster
Posts: 2
Joined: Sat Jan 31, 2004 4:12 am

100 Wrong Answer???

Post by 39949FP »

I have tried everything...
I can't see what's wrong!!!
And I am not supposing that the second number is greater than the first one.
Can anyone help me?

[c]
#include <stdio.h>
#include <unistd.h>

/* Read from standard input
Returns 0 if there's nothing there
*/
int readInput(int * min, int * max){
char aux[20];
int number=0;
int i=0;

read(0, aux, 1);
if(aux[0]<'0' || aux[0]>'9') return 0;

while(aux[i++]!='\n'){
read(0, aux+i, 1);
}

if(i==1) return 0;

for(i=0; aux>='0' && aux<='9'; i++){
number*=10;
number+=aux-'0';
}
*min=number;

number=0;
i++;
while(aux<'0' || aux>'9') i++;

while(aux!='\n'){
number*=10;
number+=aux[i++]-'0';
}
*max=number;

return 1;
}


int lengthVector[1000001];

/*Returns the cycle length of number
Fills lengthVector
*/
int getCycleLength(long long int number){
long long int nxtNumber;

if(number<1000001){
if(lengthVector[number]!=0) return lengthVector[number];

if(number%2 == 1) nxtNumber=3*number+1;
else nxtNumber = number/2;
return(lengthVector[number] = getCycleLength(nxtNumber) + 1);
}else{
if(number%2 == 1) nxtNumber=3*number+1;
else nxtNumber = number/2;

return(getCycleLength(nxtNumber) + 1);
}
}

/*Returns the greatest cycle in [min:max]
*/
int getMaxCycle(int min, int max){
int maximum = lengthVector[min];
int i = min+1;

while(i<=max){
if(lengthVector>maximum) maximum=lengthVector;
i++;
}

return(maximum);
}

int main(){
long long int i;
int min=1, max=1;

/*Zero the array*/
for(i=2; i<1000001; i++) lengthVector=0;
lengthVector[1]=1;

/*Fills all the array lengthVector*/
for(i=2; i<1000001; i++){
if(lengthVector==0){
getCycleLength(i);
}
}


/*Receiving the inputs and printing the max cycles*/
while(readInput(&min,&max)){
if(min>max) printf("%d %d %d\n", min, max, getMaxCycle(max, min));
else printf("%d %d %d\n", min, max, getMaxCycle(min,max));
}

return 0;
}
[/c]
39949FP
New poster
Posts: 2
Joined: Sat Jan 31, 2004 4:12 am

Post by 39949FP »

What's wrong with this code???
I not assuming that the fsecond is bigger...

[c]
#include <stdio.h>
#include <unistd.h>

/* Read from standard input
Returns 0 if there's nothing there
*/
int readInput(int * min, int * max){
char aux[20];
int number=0;
int i=0;

read(0, aux, 1);
if(aux[0]<'0' || aux[0]>'9') return 0;

while(aux[i++]!='\n'){
read(0, aux+i, 1);
}

if(i==1) return 0;

for(i=0; aux>='0' && aux<='9'; i++){
number*=10;
number+=aux-'0';
}
*min=number;

number=0;
i++;
while(aux<'0' || aux>'9') i++;

while(aux!='\n'){
number*=10;
number+=aux[i++]-'0';
}
*max=number;

return 1;
}


int lengthVector[1000001];

/*Returns the cycle length of number
Fills lengthVector
*/
int getCycleLength(long long int number){
long long int nxtNumber;

if(number<1000001){
if(lengthVector[number]!=0) return lengthVector[number];

if(number%2 == 1) nxtNumber=3*number+1;
else nxtNumber = number/2;
return(lengthVector[number] = getCycleLength(nxtNumber) + 1);
}else{
if(number%2 == 1) nxtNumber=3*number+1;
else nxtNumber = number/2;

return(getCycleLength(nxtNumber) + 1);
}
}

/*Returns the greatest cycle in [min:max]
*/
int getMaxCycle(int min, int max){
int maximum = lengthVector[min];
int i = min+1;

while(i<=max){
if(lengthVector>maximum) maximum=lengthVector;
i++;
}

return(maximum);
}

int main(){
long long int i;
int min=1, max=1;

/*Zero the array*/
for(i=2; i<1000001; i++) lengthVector=0;
lengthVector[1]=1;

/*Fills all the array lengthVector*/
for(i=2; i<1000001; i++){
if(lengthVector==0){
getCycleLength(i);
}
}


/*Receiving the inputs and printing the max cycles*/
while(readInput(&min,&max)){
if(min>max) printf("%d %d %d\n", min, max, getMaxCycle(max, min));
else printf("%d %d %d\n", min, max, getMaxCycle(min,max));
}

return 0;
}
[/c]
Farqaleet
New poster
Posts: 15
Joined: Wed Jan 28, 2004 11:24 pm

Post by Farqaleet »

I don't see anything wrong with the logic.

If you are getting the wrong answer reply from the judge then there can only be one thing wrong. You are assuming three things.

One that the the character set that the judge's computer is using has:
'0' - '9' as consecutive characters.

Two, that they are in the correct ascending order and not in decending or other random order.

Three and most importantly which most probably is the reason for your programs wrong answers is that you are assuming that the judge's computer uses '\n' as the line ending character in its files. Rember some files have '\r\n' which both combined give the next line character i.e. not simply line-feed but the combination of "Carriage-return, Line-feed".

If there is something else wrong, Then I can't say. The judge might even be using files that end lines with '\r' for all we know, so you can get "Time limit exceede" error too.

The second-best thing to do is to use these functions instead:
[cpp]
isspace();
isdigit();
isalpha();
sscanf();
sfprintf();
...
[/cpp]

The best thing ofcourse is to use
[cpp]
cin
scanf
[/cpp]

for reading data.
Farqaleet
New poster
Posts: 15
Joined: Wed Jan 28, 2004 11:24 pm

Post by Farqaleet »

I think I know why the judge is rejecting your program. You are not looking out for spaces at the start of the input. Put some code that skips over spaces. A better way to do it is to use
[cpp]
isspace(aux);
[/cpp]

as it skips over spaces, tabs, \r, \n etc. Really any kind of a character representing empty spaces. Also to end the program look for the EOF character because the judge redirects the stdin to a file so you will always get this as the last character of the file, so you can always know for sure that your program is not exceeding time because it is waiting for more input (maybe invalid input) to end, rather than EOF.
Klexer
New poster
Posts: 1
Joined: Thu Feb 05, 2004 7:02 pm

Post by Klexer »

I m gettin WA everytime i submit this
Pls help me :cry:

/*@JUDGE_ID: 42099PZ 100*/
#include<iostream>

using namespace std;

long findmax(long a,long b)
{
long i,j,k,temp,max,count;
if(a>b)
{
temp=a;
a=b;
b=temp;
}
max=1;
count=1;
for(i=a,j=i;i<=b;i++,j=i)
{
if(count>max)
{
max=count;
}
count=1;
while(j!=1)
{
count++;
if(j%2==0)
{
j/=2;
}
else
{
j=(3*j)+1;
}
}

}
return max;
}
main()
{
long a,b;
while(cin>>a>>b)
{
cout<<a<<" "<<b<<" ";
long x=findmax(a,b);
cout<<x<<endl;
}
}
/*@END_OF_SOURCE_CODE*/
2,17 Top
Thanx in advance
nightdog
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm

Post by nightdog »

your program does not output correctly... it should wait for the end of all the input, and then output the results by order... besides that, your program seems fine :)

good luck
JW
New poster
Posts: 6
Joined: Sat Feb 14, 2004 4:25 pm

Post by JW »

My code has got LT. Why?
[c]#include <stdio.h>

unsigned int findmaxcycle(unsigned int i, unsigned int j)
{
register unsigned int n, counter, min, max, k, p;
static cycles[999999];
counter = 1;
k = 1;
if (i > j)
{min = j; max = i;}
else
{min = i; max = j;}

for (k = min; k <= max; k++)
{
n = k;
while (n != 1)
{
if (n % 2 != 0)
n = 3*n + 1;
else
n = n / 2;
counter++;
}
cycles[k] = counter;
counter = 1;
}
for (k = min + 1, p = min; k <= max; k++)
{
if (cycles[p] < cycles[k]) p = k;
}
return cycles[p];
}

int main()
{
unsigned int i, j;

while(1) {
scanf("%d%d", &i, &j);
printf("%d %d %d\n", i, j, findmaxcycle(i, j));}
return 0;
}[/c]
nightdog
New poster
Posts: 10
Joined: Sun Jan 18, 2004 6:12 pm

Post by nightdog »

if you got a time limit exceeded from the online judge, it's probably because your algorithm is slow or inefficient in some point.. i'd suggest changing the part where you find the higher cycle length, here's a suggestion: instead of using an array to store all values of the cycle length, override the current maxcycle value if the one u just got is bigger. that way, when you end the cycle, you'll have the biggest cycle length.

[c] for(input=i;input<=j;input++) {
long int count=1,n=input;
while(n != 1) {
count++;
if((n % 2) != 0)
n = (3*n)+1;
else
n = n >> 1;

}
if(count > maxcycle)
maxcycle =count;
}[/c]

also, you are supposed to get all inputs and THEN output the results.
Post Reply

Return to “Volume 1 (100-199)”