100 - The 3n + 1 problem

[MAK]

Suggestions:
Use Scanner for input
Use longs (the problem statement talks of 32bit ints. Java ints are 32 bits but they are signed so they are effectively 31 bits for positive numbers)
Get rid of this line
if(num1>10000||num2>10000||num1<0||num2<0)break;
Input is guaranteed to be valid, so no need to check. Actually this causes WA because input can be as large as 999999

Everyone gets lots of WA/TLE/CE at first, that is no reason to feel frustrated.

Hope this helps

[mf]

Use Scanner for input

Actually, Scanner is quite a bit slower than BufferedReader + StringTokenizer combo.

Use longs (the problem statement talks of 32bit ints. Java ints are 32 bits but they are signed so they are effectively 31 bits for positive numbers)

It doesn't matter in this problem.


I'd suggest to replace % and / in 'if((i%2)==1) i=i*3+1; else i=i/2;' by bitwise operators:

Code: Select all

if ((i & 1) == 1)
    i = i * 3 + 1;
else
    i >>= 1;

[dreadlord]

printf ("Hello, world\n");

I've thought that a possible method to improve efficiency in this algorithm could be to store not only cycle values for numbers as they are being computed, but also the maximum of each one of the input intervals.

This could help to save time if further intervals may be decomposed in pieces and some of these pieces are already computed intervals, but this means that a proper data structure should be maintained to store and query already computed intervals, so if further intervals cannot be decomposed into already computed ones, or this info is of little help, it could be even more expensive in terms of time.

Any of you have already tried or considered this? Any clue about whether it could worth the effort?

Thanks!

[newton]

Your calling function is killling much more time.
It would be better if u compute data inside of main.
Try avoiding java, its functions are time killer.

[crr]

Hi guys....odd thing. On the programming-challenges.com site I get WA, with this code (not sure why, it works with the sample inp file, and it works with j>i) but over here I get a runtime error. It's ANSI C and I'm returning 0 at the end, so I'm not sure what it's not liking. Can anyone point me in the right direction? Here's the code:

Code: Select all

/* program to find the maximum cycle count for the solution of the 3n+1 
 * problem for a series of numbers defined by bounds as entered from 
 * stdin, inclusive.*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TESTING 0
#define DEBUG 0
#define MAXNUM 1000
#define BASECOUNT 1

int processNumber (int num);

int main(void) {

	int a[MAXNUM], b[MAXNUM], i, j, n;		/*upper and lower bounds and current number working on*/
	int count, maxcount, entrycount = 0;		/*cycle count and max count for this dataset*/
	char s[17];					/*holds the string read in from stdin*/

	while((fgets(s, 17, stdin)) != (char *)0){
		a[entrycount] = atoi(strtok(s, " "));	/*take the string, tokenise it, then convert to int*/
		b[entrycount] = atoi(strtok(NULL, " "));
		entrycount++;
	}
	entrycount--;					/*don't want the EOF as our final entry*/
	
	int m;		/*counter*/	
	for (m=0;m<=entrycount;m++) {
		maxcount = 0;

		if (b[m]>=a[m]) {
			i = a[m];
			j = b[m];
			if (TESTING) printf("a=%d, b=%d, i=%d, j=%d\n", a[m], b[m], i, j);
			for (i;i<=j;i++){
				count = BASECOUNT;
				n = i;
				while (n>1) {
					++count;
					n = processNumber(n);
				}
				if (TESTING) printf("count for number %d is %d\n", i, count);
				if (count > maxcount)
					maxcount = count;
			}
		}
		else {
			j = a[m];
			i = b[m];
			if (TESTING) printf("a=%d, b=%d, i=%d, j=%d\n", a[m], b[m], i, j);
			for (i;i<=j;i++){
				count = BASECOUNT;
				n = i;
				while (n>1) {
					++count;
					n = processNumber(n);
				}
				if (TESTING) printf("count for number %d is %d\n", i, count);
				if (TESTING) break;
				if (count > maxcount)
					maxcount = count;
			}
		}
		printf("%d %d %d\n", a[m], b[m], maxcount);
	}
	return 0;
}

int processNumber(int num) {
	
	if (DEBUG) printf("***Entered processNumber, num is %d\n", num);
	if (num % 2 == 0) {
		num = num / 2;
	}
	else {
		num = (3 * num) +1;
	}
	return num;
}

[mf]

I guess it's either because your constant MAXNUM is too low, or some lines in the input are larger than 17 characters (with many extra whitespaces), or both.

To fix the first problem, don't try to read all the input at once. Instead, read a single input test case (two integers), solve it, output answer, then read the next case in a loop, etc.

As for the second one, just use scanf("%d %d", &a, &b) instead of all that gets/strtok/atoi stuff.

[clearner]

Hi, someone who can give me a hand, just don't know why it always show runtime error with my c program. Here is my codes:

Code: Select all

#include <stdio.h>

int Q(int n)
{
   int cyclelength=1;

   while(n>1)
   {
     if((n%2)==1) {
        n=3*n+1;
     }
     else n = n/2;
        cyclelength++;
   }
   return cyclelength;
}

int main()
{
    int  a, b, i, t, max_clength;

    while(scanf("%d %d", &a, &b)==2) {
       printf("%d %d ", a, b);
       if(a>b){
         t=a; a=b; b=t;
       }
       max_clength=0;
       for(i=a; i<=b; i++){
           t = Q( i );
           if(t > max_clength)  max_clength=t;
       }
       printf("%d\n", max_clength);
    }
}

[mf]

main() must return 0.

With right options (for gcc: -W -Wall), your compiler would already warn you about that.

[Stachelsk]

I looked over the sticky, and yes, my program accounts for the fact that is it possible for i > j.
I've tried comparing my answers to "accepted solutions" and other source code that has worked to no avail.

Code is in ANSI C.

Code: Select all

#include <stdio.h>

#define TABLE_SIZE 1000000
int calculated [TABLE_SIZE];

/* -------------------------------------------------------------------------- */
/*  Recieves input from the user, spits back output                           */
/* -------------------------------------------------------------------------- */
int main (int argc, const char * args[]) {

	int a, b, low, high, max;

	while(!feof(stdin)) {
		scanf("%d %d", &low, &high);
		a = low, b = high;
		
		/* ------------------------------------------------------------------ */
		/*  Perform some quick checks to prevent runtime errors.              */
		/* ------------------------------------------------------------------ */
		if(low > high) {
			int temp = high;
			high = low;
			low = temp;
		}
		
		max = cycleLength(low);
		
		/* ------------------------------------------------------------------ */
		/*  Now start scanning through the range to find the maximum.		  */
		/* ------------------------------------------------------------------ */
		int counter;
		for(counter = (low+1); counter <= high; counter++) {
			calculated[counter] = cycleLength(counter);
			
			if(calculated[counter] > max)
				max = calculated[counter];
		}
		
		printf("%d %d %d\n", a, b, max);
	}
	
    return 0;
}

/* -------------------------------------------------------------------------- */
/*  Determines the cycle length for a given integer.						  */
/*																			  */
/*  The value is looked up in each instance to see if it has already been	  */
/*  calculated (in order to save processing time). If the value has not been  */
/*  precalculated, it is save once it is calculated.						  */
/* -------------------------------------------------------------------------- */
int cycleLength(unsigned int num) {

	if(num < TABLE_SIZE)
		if(calculated[num] != 0)
			return calculated[num];

	if(num != 1)
		return (num&1) ? 1 + cycleLength(num*3 + 1) : 1 + cycleLength(num/2);
	
	else return 1;
}

Thanks in advance!!

Edit: Getting WA (Wrong Answer) as a result.

[Jan]

Search the board first. And use an existing thread.

[Chirag Chheda]

Can some one help me with better algo??? to get accepted quicker.

Think of using DP in this question.
Well ,now i think u can figure out the solution yourself.

Bye

[MAK]

Function calls are certainly not eating up your time. Instead of using two scanners, why don't you use nextInt() on the first scanner? Maybe declaring the Scanner as

Code: Select all

Scanner getInput=new Scanner(new BufferedInputStream(System.in));

might also help.

Java is slower than C++, but this does not really matter unless it is backtracking problem or a problem involving huge I/O. Java function calls aren't all that different from calls in other languages and in this case the calls aren't even nested, so there is only one call made per test case (which therefore add just a constant, and very small, overhead).

I originally solved this problem in the old judge, and actually had to implement my own buffered scanner-like method for it .

[lnr]

Yes DP and sorting may do it.

[mrmrumman]

My code is like this:

Code: Select all

# include <stdio.h>

int main()
{
	
	int i=0,one, two, max=0;
	scanf("%d %d",&one,&two);
	int j=one;
	while(j<=two)
	{
		one=j;
		i=0;
		while(one!=1)
		{
			if(one%2==0)
			{
				one=one/2;
				i++;
			}
			else if(one%2==1)
			{
				one=3*one+1;
				i++;
			}
		}
		i++;/*for one=1*/
		if(max>i)
			max=max;
		else
			max=i;
		j++;
	}
	printf(" %d",max);
	return 0;
}

Anyone can tell me why it is not working?

[mrmrumman]

My code is like this:

Code: Select all

# include <stdio.h>

int main()
{
	
	int i=0,one, two, max=0;
	scanf("%d %d",&one,&two);
	int j=one;
	while(j<=two)
	{
		one=j;
		i=0;
		while(one!=1)
		{
			if(one%2==0)
			{
				one=one/2;
				i++;
			}
			else if(one%2==1)
			{
				one=3*one+1;
				i++;
			}
		}
		i++;/*for one=1*/
		if(max>i)
			max=max;
		else
			max=i;
		j++;
	}
	printf(" %d",max);
	return 0;
}

I submitted it but they don't accept it. Anyone can tell why?