## 100 - The 3n + 1 problem

Moderator: Board moderators

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

### Re: problem 100 TLE in java?

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?

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;``````

New poster
Posts: 19
Joined: Sat Apr 19, 2008 11:19 pm

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

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
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 100 Time Limit Exceeded

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.
http://www.newton.0fees.net is enough! 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!

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;					/*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!

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

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

main() must return 0.

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

### Problem 100

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;
}``````

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: Problem 100

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

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

### Re: 100 Time Limit Exceeded

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

### 100:The 3n+1 Problem

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

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

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