100 - The 3n + 1 problem

[silverlining]

No idea sorry. But try testing it out with your own numbers and see how far its off. Maybe that'll give you a clue on what's wrong.

[mf]

long i = Long.parseLong(str.split(" ")[0]);
long j = Long.parseLong(str.split(" ")[1]);

This is wrong, because there may be leading or trailing spaces, and more than one space between the numbers.

catch (Exception e){
System.exit(0);
}

You don't have to catch exceptions, testing system does that for you. And when it catches exception, it gives you a more meaningful response - "runtime error", instead of "wrong answer".

[vizardo]

This is my new version of the code and i got back Time Limit Exceeded...

Code: Select all

import java.util.Scanner;

public class Main{
	
	public static long cycle_length(long num){
		long count = 1;
		
		while (num != 1){
			if (num%2 == 0){
				num = num / 2;
			}
			else{
				num = num * 3 + 1;
			}
			count++;
		}
		
		return count;
	}
	
	public static void main(String args[]){
		try{
			Scanner scanner = new Scanner(System.in);
			
			long i = scanner.nextLong();
			long j = scanner.nextLong();
			
			while (true){				
				long a;
				long b;
				
				if (i < j){
					a = i;
					b = j;
				}
				else{
					a = j;
					b = i;
				}
				
				
				long max = 0;
				
				for (long k = a; k <= b; k++){
					long temp = cycle_length(k);
					if (max < temp){
						max = temp;
					}
				}
				
				System.out.println("" + i + " " + j + " " + max);
				
				i = scanner.nextLong();
				j = scanner.nextLong();
			}
		}
		catch (Exception e){
			System.exit(0);
		}
	}
}

I think the problem is because i use while(true) which makes the loop infinite. That's why I use the catch exception to exit the program when there's no more input (assume that the judge will use a text file as input file). So the question is when should I terminate the program? Normally, they should mention sth like when we input this number or that number then the program is terminated. However, in this case, they don't mention anything like that. So how can i know when to terminate the program?

[mf]

Oh, OK, that should work. Though you could have used hasNextLong() method of java.util.Scanner instead, too.

'Time limit exceed' is because your program is too slow. Here are a few suggestions how to make it faster:
1) Replace num%2 and num/2 by num&1 and num>>1.
2) Use int instead of long.
3) Scanner is quite slow, use BufferedReader and StringTokenizer, or StreamTokenizer instead.

[vizardo]

I have changed my code based on what you suggested but i still got back time limit exceeded.. .. i'm stuck now.. please help!!

Code: Select all

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	
	public static int cycle_length(int num){
		int count = 1;
		
		while (num != 1){
			if ((num & 1) == 0){
				num = num>>1;
			}
			else{
				num = (num<<1) + num + 1;
			}
			count++;
		}
		
		return count;
	}
	
	
	public static void main(String args[]) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());
		
		while (token.hasMoreTokens()){
			int i = Integer.parseInt(token.nextToken());
			int j = Integer.parseInt(token.nextToken());
			
			int max = 0;
			
			int a = Math.min(i, j);
			int b = Math.max(i, j);
			
			System.out.println("" + i + " " + j);
			for (int k = a; k <= b; k++){
				int temp = cycle_length(k);
				if (max < temp){
					max = temp;
				}
			}
			
			System.out.println("" + i + " " + j + " " + max);

			token = new StringTokenizer(br.readLine());
		}
		
		br.close();
	}
}

[mf]

Time limit, you say? It should get runtime error. Did you submit the wrong code?

[vizardo]

oops... sorry.. my clumsy mistake... i submitted the wrong code... now it's correct already.. hehe.. thanks a lot for your help! very appreciate it! Here is the final version of my code...

Code: Select all

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	
	public static int cycle_length(int num){
		int count = 1;
		
		while (num != 1){
			if ((num & 1) == 0){
				num = num>>1;
			}
			else{
				num = (num<<1) + num + 1;
			}
			count++;
		}
		
		return count;
	}
	
	
	public static void main(String args[]){
		try{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer token = new StringTokenizer(br.readLine());
			
			while (token.hasMoreTokens()){
				int i = Integer.parseInt(token.nextToken());
				int j = Integer.parseInt(token.nextToken());
				
				int max = 0;
				
				int a = Math.min(i, j);
				int b = Math.max(i, j);
				
				for (int k = a; k <= b; k++){
					int temp = cycle_length(k);
					if (max < temp){
						max = temp;
					}
				}
				
				System.out.println("" + i + " " + j + " " + max);
	
				token = new StringTokenizer(br.readLine());
			}
			
			br.close();
		}
		catch(Exception e){
			System.exit(0);
		}
	}
}

[jpaul]

Scanner is a practical class for read data from a stream o string... but it slower. Scanner use regular expressions for match the elements in the input. The regular expression is powerful way for matching strings and another streams, but this tecnology is very slower. If you know how is the input... then you don't need match for each elements in the input... e.g. If you know that the input in one line is:
String String Double Double
then you can use the next form:

Code: Select all

public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        // Another variables
        StringTokenizer st;
        String sa, sb;
        double da, db;
        // Another variables

        // Some of code ...
        // Some of code ...
        st = new StringTokenizer(in.readLine());
        sa = st.nextToken(); // String
        sb = st.nextToken(); // String
        da = Double.parseDouble(st.nextToken()); // Double
        db = Double.parseDouble(st.nextToken()); // Double
        // Some of code
        // Some of code ...

        out.flush();
 }

The output have another similarities...
If the automatic flush is on, then have a cost of runtime... It's preferible disabled... and use out.flush() in the finalline in you code...

[naga]

#include <stdio.h>

unsigned long int problem(unsigned long int n)
{
if(n==1)
{
return 1;
}
else
{
if(n%2!=0)
{
return 1 + problem(3*n + 1);
}
else
{
return 1 + problem(n/2);
}
}
}


int main()
{
unsigned long int start,end,i,j,result,max_cycle;
while(scanf("%d %d",&i,&j) == 2)
{
start = i;
end = j;
max_cycle = 0;
if(i > j)
{
unsigned int t;
t = start ;
start = end;
end = t;
}
//performing the algorithm
for(start ; start <=end; start++)
{
result = problem(start);
max_cycle = max_cycle < result ? result : max_cycle;
}
printf("%d %d %d\n", i, j, max_cycle);
}
return 0;
}

Here is my Solution ,I always get a WA.Please help

[luiggixd]

Hi people, I have problems with this problem.

This is my code and it gives me Runtime Exception

Code: Select all

#include <stdio.h>
#include <stack.h>
#include <list.h>
#include <string.h>
#define MAX 1000001
int main()
{
  int *Vector, max, n1, n2;
  Vector = new int[MAX];
  memset(Vector, 0, sizeof(Vector));
  n1 = n2 = 1;
  while(n1 < max)
  {
    Vector[n1] = n2;
    n2++;
    n1*=2;
  }
  stack<int,list<int> > stack;
  while(1)
  {
	  if (scanf("%d %d", &n1, &n2) == EOF)
      break;
  	printf("%d %d ", n1, n2);
    n2++;
    max = 0;
    for(int i=n1; i<n2; i++)
    {
      int k = i, cont = Vector[i];
      if (cont == 0)
      {
        while(k>1)
        {
          stack.push(k);
          k = (k % 2 == 0)?(k/2):(3*k+1);
          cont = Vector[k];
          if (cont > 0)
          {
            k = 1;
          }
        }
        while(!stack.empty())
        {
          Vector[stack.top()] = ++cont;
          stack.pop();
        }
      }
      max = (max<cont)?cont:max;
    }
    printf("%d\n", max);
  }
  free(Vector);
  return 0;
}

Can you help me please?

Thanks

[mf]

Did you even test your program? A few obvious errors are here:

Code: Select all

  int *Vector, max, n1, n2;
  Vector = new int[MAX];
  memset(Vector, 0, sizeof(Vector));
  n1 = n2 = 1;
  while(n1 < max) {
...
  free(Vector);

sizeof(Vector) is always 4, or maybe 8.
max is used uninitialized.
You allocate memory with `new[]', but free it with `free()'.


And does it even compile? I got a ton of errors.

[luiggixd]

Ok sorry, some bugs... but I fixed all of that and still got RE. Can you tell me please what could be a greater bug than all those? I tested and it's OK (running on Windows XP) I even tested it in cygwin I'm out of mind.

Code: Select all

// FIXED CODE
#include <stdio.h>
#include <stack.h>
#include <list.h>
#include <string.h>
#define MAX 1000001
int main()
{
  int *Vector, max, n1, n2;
  Vector = new int[MAX];
  memset(Vector, 0, MAX*sizeof(Vector));
  n1 = n2 = 1;
  while(n1 < MAX)
  {
    Vector[n1] = n2;
    n2++;
    n1*=2;
  }
  stack<int,list<int> > stack;
  while(1)
  {
	if (scanf("%d %d", &n1, &n2) == EOF)
      break;
  	printf("%d %d ", n1, n2);
    n2++;
    max = 0;
    for(int i=n1; i<n2; i++)
    {
      int k = i, cont = Vector[i];
      if (cont == 0)
      {
        while(k>1)
        {
          stack.push(k);
          k = (k % 2 == 0)?(k/2):(3*k+1);
          cont = Vector[k];
          if (cont > 0)
          {
            k = 1;
          }
        }
        while(!stack.empty())
        {
          Vector[stack.top()] = ++cont;
          stack.pop();
        }
      }
      max = (max<cont)?cont:max;
    }
    printf("%d\n", max);
  }
  delete Vector;
  return 0;
}

I tryed this other code, and still RE

Code: Select all

#include <vector.h>
int main()
{
  int max, n1, n2;
  vector<int> myVector(MAX);
  max = MAX;
  n1 = n2 = 1;
  while(n1 < max)
  {
    myVector[n1] = n2;
    n2++;
    n1*=2;
  }
  stack<int,list<int> > stack;
  while(1)
  {
    if (scanf("%d %d", &n1, &n2) == EOF)
      break;
    printf("%d %d ", n1, n2);
    n2++;
    max = 0;
    for(int i=n1; i<n2; i++)
    {
      int k = i, cont = myVector[i];
      if (cont == 0)
      {
        while(k>1)
        {
          stack.push(k);
          k = (k % 2 == 0)?(k/2):(3*k+1);
          cont = myVector[k];
          if (cont > 0)
          {
            k = 1;
          }
        }
        while(!stack.empty())
        {
          myVector[stack.top()] = ++cont;
          stack.pop();
        }
      }
      max = (max<cont)?cont:max;
    }
    printf("%d\n", max);
  }
  return 0;
}

Help...

[mf]

I still get errors like 'stack.h: No such file or directory' and 'list.h: No such file or directory'. Where did you even find them? For over a decade STL include files don't end in '.h' - you should use just #include <stack> and #include <list> instead, and also specify "using namespace std;".

I've fixed that and tried running your program under gdb.

First error is here:

int *Vector, max, n1, n2;
Vector = new int[MAX];
memset(Vector, 0, MAX*sizeof(Vector));

I'm using 64-bit machine, here sizeof(Vector)==8, and sizeof(int)==4, so you pass wrong amount of memory to memset. Use memset(Vector, 0, MAX*sizeof(Vector[0])); instead.

Another error occurred here:

Code: Select all

              Vector[stack.top()] = ++cont;

with stack.top()==1276936.

Apparently, you assume that all generated numbers in 3n+1 sequences will be at most 1000000. Well, that's not the case. You can only assume that they fit in 32-bit signed integer, i.e. are at most 2^31-1.

This is also wrong:

delete Vector;

You allocated memory with 'new int[MAX]', so you must use 'delete[] Vector' here.

And it's better to replace the following code:

Code: Select all

      while(1)
      {
       if (scanf("%d %d", &n1, &n2) == EOF)
          break;

with

Code: Select all

while (scanf("%d %d", &n1, &n2) == 2) {

[amir.shani]

Hi,

I submitted my first 100 solution which ran in 0.608 (ANSI C)
I submitted my improved 100 solution which ran in 0.044 (ANSI C)

but I saw that there are people with runtime of 0.000 , how is that even possible ?!?!
here is my improved solution, can you help me make it run faster ?

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

#define ARR_SIZE 1000000

typedef struct node_t
{
unsigned long data;
struct node_t* next;

}node;

void computeIterations(unsigned long n, unsigned long* memory)
{
node *tmp;
node *head;
unsigned long i;

if ((n < ARR_SIZE) && (memory[n] != 0))
return;

head = (node*)malloc(sizeof(node));
head->data = n;
head->next = NULL;

while ( (n>= ARR_SIZE) || (memory[n] == 0))
{
tmp = (node*)malloc(sizeof(node));
tmp->next = head;
head = tmp;
head->data = (n&1) ? 3*n + 1 : n >> 1;
n = head->data;
}

i = memory[head->data];
tmp = head;
head = head->next;
free(tmp);

while (head != NULL)
{
i++;
if (head->data < ARR_SIZE)
memory[head->data] = i;

tmp = head;
head = head->next;
free(tmp);
}

return;
}



int main()
{
unsigned long *memory ,index;
unsigned long i,j,k,n,cycles,max_cycles = 0;

memory = (unsigned long *)malloc(ARR_SIZE * sizeof(unsigned long));
memset((void*)memory,0, ARR_SIZE * sizeof(unsigned long));
memory[1] = 1;


while (2 == scanf("%li %li",&i,&j))
{
printf ("%li %li ", i , j);
if (i>j)
{
i += j;j = i - j;i -= j;
}

for (k = i ; k <= j ; k++)
{
computeIterations(k,memory) ;
if (max_cycles < memory[k])
max_cycles = memory[k];
}

printf("%li\n",max_cycles);
max_cycles = 0;
}

return 0;


}

[mf]

Please use

Code: Select all

 tags when posting code, so that indentation isn't lost.

[quote]but I saw that there are people with runtime of 0.000 , how is that even possible ?!?!
here is my improved solution, can you help me make it run faster ?[/quote]
I wouldn't worry about running time. This site is about improving your algorithmic and problem solving skills, and not about low level optimizations.

[quote]but I saw that there are people with runtime of 0.000 , how is that even possible ?!?![/quote]
Definetely some kind of precomputation, or maybe they've just mined judge's input.

Using a simple precomputed table with maximums on every interval of 100 numbers I've got 0.008 seconds (table takes about 36Kb, and source size limit is 40Kb, I think).