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

MAK
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Re: problem 100 TLE in java?

Post by MAK » Sat May 31, 2008 11:36 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: problem 100 TLE in java?

Post by mf » Sun Jun 01, 2008 11:01 am

MAK wrote: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
New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

Re: If you get WA in problem 100, read me before post!

Post by dreadlord » Fri Jun 06, 2008 12:46 pm

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!

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 100 Time Limit Exceeded

Post by newton » Mon Jun 09, 2008 10:15 pm

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
New poster
Posts: 1
Joined: Sat Jun 14, 2008 1:30 am

Re: If you get WA in problem 100, read me before post!

Post by crr » Sat Jun 14, 2008 2:09 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: If you get WA in problem 100, read me before post!

Post by mf » Sat Jun 14, 2008 8:14 pm

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
New poster
Posts: 1
Joined: Sat Jun 21, 2008 9:27 pm

Re: 100

Post by clearner » Sat Jun 21, 2008 9:39 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 100

Post by mf » Sat Jun 21, 2008 9:59 pm

main() must return 0.

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

Stachelsk
New poster
Posts: 1
Joined: Sun Jun 22, 2008 8:24 pm

Problem 100

Post by Stachelsk » Sun Jun 22, 2008 8:28 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: Problem 100

Post by Jan » Sun Jun 22, 2008 11:07 pm

Search the board first. And use an existing thread.
Ami ekhono shopno dekhi...
HomePage

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 100

Post by Chirag Chheda » Fri Jun 27, 2008 12:49 pm

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
New poster
Posts: 28
Joined: Sun Oct 23, 2005 3:44 pm
Location: Dhaka, Bangladesh

Re: 100 Time Limit Exceeded

Post by MAK » Tue Jul 01, 2008 11:00 pm

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
Experienced poster
Posts: 142
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

100:The 3n+1 Problem

Post by lnr » Wed Jul 02, 2008 2:51 pm

Yes DP and sorting may do it.

mrmrumman
New poster
Posts: 10
Joined: Sat Jul 05, 2008 11:26 pm
Location: Dhaka
Contact:

Why my code is not working

Post by mrmrumman » Sat Jul 05, 2008 11:36 pm

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?
R|_|\/|\/|/-\|\|

mrmrumman
New poster
Posts: 10
Joined: Sat Jul 05, 2008 11:26 pm
Location: Dhaka
Contact:

I am facing a problem

Post by mrmrumman » Sat Jul 05, 2008 11:49 pm

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?
R|_|\/|\/|/-\|\|

Post Reply

Return to “Volume 1 (100-199)”