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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: input error in 3n+1 problem

Post by brianfry713 » Tue Feb 12, 2013 10:01 pm

Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: RUN TIME ERROR on Problem 100

Post by raj » Mon Feb 18, 2013 5:56 pm

online judge says its RUN TIME ERROR..........
can anyone please help me to find out the problem......... :(

import java.io.*;
import java.util.*;
public class Main{
public static void main(String [] args)throws IOException{
final BufferedReader k = new BufferedReader(new InputStreamReader(System.in));
PrintWriter z = new PrintWriter(System.out);
int min = 0,max = 0;
while(true)
{
int r = 0;
int n = 0,m = 0;
StringTokenizer s = new StringTokenizer(k.readLine());
while(s.hasMoreTokens())
{
n = Integer.valueOf(s.nextToken());
m = Integer.valueOf(s.nextToken());
}
if(n>m)
{
max = n;
min = m;
}
else
{
max = m;
min = n;
}
while(min<=max)
{
int cycle = 0;
int i = min;
while(i != 1)
{
if(i%2==0)
{
i = i/2;
}
else
{
i = 3*i + 1;
}
cycle++;
}
min++;
if(r<cycle)
{
r = cycle;
}
}
z.println(n+" "+m+" "+(++r));
z.flush();
}
}
}

Pete_Aye
New poster
Posts: 2
Joined: Tue Feb 19, 2013 9:28 am
Location: Jos, Nigeria

TLE in 3n+1 Problem. Why?

Post by Pete_Aye » Tue Feb 19, 2013 9:49 am

Please can anyone tell me why this code is giving me TLE, and how I can make it Accepted?

Code: Select all

#include <iostream>

using namespace std;

int main(){
	int start, stop, stopHold;
	while(true){
		std::cin >> start  >> stop;
		if(start > 1000000 || start <= 0 || stop > 1000000 || stop <= 0){
			break;
		}
		stopHold = stop;
		int max = 0;
		int counter = 1;
		int i;
		int temp = stop;
		do{
			i = temp;
			counter = 1;
			while(i > 1){
				counter++;
				if(i%2 == 0){
					i /= 2;
				}else{
					i = i * 3 + 1;
				}
			}
			if(max < counter){
				max = counter;
			}
			temp--;
		}while(temp > start);
		std::cout << start << " " << stopHold << " " << max << std::endl;
	}
	return 0;
}

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Re: TLE in 3n+1 Problem. Why?

Post by Darko » Tue Feb 19, 2013 10:40 pm

There is a sticky thread in Volume I but one of the problems you have is that you assume start <= stop.

Pete_Aye
New poster
Posts: 2
Joined: Tue Feb 19, 2013 9:28 am
Location: Jos, Nigeria

Re: TLE in 3n+1 Problem. Why?

Post by Pete_Aye » Wed Feb 20, 2013 1:36 am

Darko wrote:There is a sticky thread in Volume I but one of the problems you have is that you assume start <= stop.
Yes, I noticed that from reading other threads, and I have corrected that error. The issue is that now the code is working, and I tested it with the n =1000000 case and there was no 'TLE'. So why am I gettting that on the judge?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Re: TLE in 3n+1 Problem. Why?

Post by Darko » Wed Feb 20, 2013 4:45 am

I am not sure how you think you fixed the start>stop issue but it is not fixed in the code you posted.
Try
999999 1

I am not familiar with C++ that much but I am not sure that is how you determine that you reached the end of file.

There is a link to a C solution (if you click around the site):
http://online-judge.uva.es/problemset/data/p100.c.html

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: WA on Problem 100

Post by brianfry713 » Wed Feb 20, 2013 11:49 pm

After the sample input your code gives this RE:
Exception in thread "main" java.lang.NullPointerException
at java.util.StringTokenizer.<init>(StringTokenizer.java:199)
at java.util.StringTokenizer.<init>(StringTokenizer.java:236)
at Main.main(Main.java:12)

You should check if k.readline() returns NULL before passing it to StringTokenizer.
Check input and AC output for thousands of problems on uDebug!

ferry6
New poster
Posts: 2
Joined: Sat Feb 23, 2013 9:43 am

Re: Newbie can't get AC

Post by ferry6 » Sat Feb 23, 2013 9:48 am

Hi I am new here.

MewCatcher
New poster
Posts: 19
Joined: Tue Oct 30, 2012 8:19 am

Re: Newbie can't get AC

Post by MewCatcher » Sat Feb 23, 2013 3:19 pm

Specific problem should be asked in corresponding board.
Best wishes!~

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: Newbie can't get AC

Post by DD » Mon Feb 25, 2013 7:49 am

There is a thread discussing about 100 where contains all solutions for different languages. You should check that.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

rabeeea2
New poster
Posts: 1
Joined: Fri Mar 01, 2013 12:46 am

why WA 3n+1

Post by rabeeea2 » Fri Mar 01, 2013 12:51 am

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

public static void main(String[] args) throws IOException {
new Main().run();
reader.close();
}

void run() throws IOException {
try {

String[] str = reader.readLine().trim().split(" ");
while (!str[0].equals("")) {

long a = Long.parseLong(str[0]);
long b = Long.parseLong(str[1]);
long max = Math.max(a, b);
long resultt = 0;
long mini = Math.min(a, b);
for (long i = max; i >= mini; i--) {
long solved = 1;
long num = i;
while (num != 1) {

if (num % 2 == 0) {
num = num / 2;
} else {
num = num * 3 + 1;
}
solved = solved + 1;
}
resultt = (solved > resultt ? solved : resultt);
}

if (max != 1) {
System.out.println(a + " " + b + " " + resultt);
} else {
System.out.println(a + " " + b + " " + 0);
}
str = reader.readLine().trim().split(" ");

}
} catch (Exception e) {
}
}
}
:evil: :evil: :evil: :evil: :evil: :evil: :evil:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: why WA 3n+1

Post by brianfry713 » Fri Mar 01, 2013 2:47 am

Input:

Code: Select all

1 1
Correct output:

Code: Select all

1 1 1
Check input and AC output for thousands of problems on uDebug!

Munchor
New poster
Posts: 19
Joined: Sun Mar 03, 2013 4:03 pm

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

Post by Munchor » Sun Mar 03, 2013 4:06 pm

Code: Select all

#include <stdio.h>
#include <vector>

using namespace std;

vector<vector<int> > intervals;
vector<unsigned int> cycles;

int max(unsigned int a, unsigned int b)
{
 return a > b ? a : b;
}

int min(unsigned int a, unsigned int b)
{
 return a < b ? a : b;
}

int get_cycle_length(unsigned int n, unsigned int cycle)
{
  if (n == 1)
    return cycle;

  if (n % 2 == 0)
  {
    n = n / 2;

    if (n < 999999 && cycles[n])
      return cycles[n] + cycle;

    get_cycle_length(n, cycle + 1);
  }
  else
  {
    n = 3 * n + 1;
    
    if (n < 999999 && cycles[n])
      return cycles[n] + cycle;

    get_cycle_length(n, cycle + 1);
  }
}

int main()
{
  unsigned int a, b;
  vector<int> interval(2);

  while (scanf("%d %d", &a, &b) != EOF)
  {
    interval[0] = a;
    interval[1] = b;
    intervals.push_back(interval);
  }

  unsigned int i;
  for (i = 1; i < 999999; i++)
  {
    cycles.push_back(0);
  }

  /* Bottom up - fill all cycle lengths */
  for (i = 1; i < 999999; i++)
  {
    cycles[i] = get_cycle_length(i, 1);
  }

  /* Go through every interval, and for each one go from smaller
     number to bigger number and find out the largest cycle length.

     Print 'i' and 'j' on the same order they were given.*/
  
  unsigned int max_so_far, u, start_on, end_on;
  for (i = 0; i < (int) intervals.size(); i++)
  {
    start_on = min(intervals[i][0], intervals[i][1]);
    end_on = max(intervals[i][0], intervals[i][1]);
    max_so_far = cycles[start_on];
    
    for (u = start_on + 1; u <= end_on; u++)
    {
      if (u < 999999)
        max_so_far = max(max_so_far, cycles[u]);
      else
        max_so_far = max(max_so_far, get_cycle_length(u, 1));
    }

    printf("%d %d %d\n", intervals[i][0], intervals[i][1], max_so_far);
  }

  return 0;
}
I am not assuming that i > j or j > i, my code works for all cases. For this critical input I made:

Code: Select all

1 1
1 10
9 11
8 12
100 200
201 210
900 1000
1000 900
999999 999990
1 999999
999999 1
I get:

Code: Select all

1 1 1
1 10 20
9 11 20
8 12 20
100 200 125
201 210 89
900 1000 174
1000 900 174
999999 999990 259
1 999999 525
999999 1 525
./threenplusone < threenplusone_input.txt  0.18s user 0.01s system 98% cpu 0.199 total
I'm running "time" so you can see it runs in very good time, under a second. However, I get Wrong Answer. Any ideas?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » Tue Mar 05, 2013 1:00 am

Check the PM I just sent you, cycles only had 999998 elements, but you used cycles[999998].
Check input and AC output for thousands of problems on uDebug!

triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

problem no 100 Time Limit Exceeded

Post by triplemzim » Sat Apr 06, 2013 6:45 pm

Here is my code:
#include<stdio.h>
int len(int x)
{
int max;
max=1;
while(x>1)
{
max++;
if(x%2==0) x=x/2;
else x=3*x+1;

}
return max;
}
int main()
{
int i,prev,a,b,max,num1,num2;
while(1){
scanf("%d %d",&num1,&num2);
prev=num1;
a=len(prev);
for(i=num1;i<num2;i++)
{

b=len(i+1);
if(a>b)
{
max=a;
}
else
{
max=b;
prev=i+1;
a=b;
}
}
printf("%d %d %d\n",num1,num2,max);
}
}

This program takes less than two seconds to find the longest chain between 1 to 1000000. But after submitting it says time limit exceeded. why?

Post Reply

Return to “Volume 1 (100-199)”