100 - The 3n + 1 problem

[Anunnaki]

Try giving your program an input with i=1, j=1000000 - it'll take many hours to complete, which is too much. Time limit is only 3 seconds.

Is there a way to do it, other than going through each individual number until j? There must be, because if not, then I can't see how you could do it in less than 3 seconds.

And don't print any extra messages, because your program's output is checked automatically by a quite dumb robot. Only output what problem statement tells you - a line with three numbers in it, for each input case.

Also you don't have to do any error checking. Even if there's any error in the input (and there isn't), nobody will read any of those error messages. If you want to get a feedback from judge on these errors, use assert() macro.

Thanks for the advice.

[mf]

Is there a way to do it, other than going through each individual number until j?

Actually that's good enough to get accepted. The problem with your code is that it does a lot of unnecessary work on lines 41-45 at each iteration, which severely affects its runtime - makes it quadratic instead of linear.

[Anunnaki]

Is there a way to do it, other than going through each individual number until j?

Actually that's good enough to get accepted. The problem with your code is that it does a lot of unnecessary work on lines 41-45 at each iteration, which severely affects its runtime - makes it quadratic instead of linear.

Okay, I changed my calculation function to this:

Code: Select all

int nCalc (int i, int j)
{
    int n, a = 0;
  //  vector<int> x;

    do
    {
            int di = i;

            for (n = 1; di != 1; n++)
            {

                    if (n == 1)
                    {
                            continue;
                    }

                    if ((di % 2) != 0)
                    {
                            di = (3 * di) + 1;
                            continue;
                    }
                    
                    else
                    {
                            di = di/2;
                    }

					if (n > a)
						a = n;
            }

            if (i == 1)
                    n = 1;

            //x.push_back(n);

/*
            for (int counter = 0; counter < x.size(); counter++)
            {
                    if (x[counter] > a)
                            a = x[counter];
            }
*/

            i++;
    }while(i <= j);

    return a;
}

However, it's acting strange. It can calculate any number instantaneously, up to 113,381. ONE number higher, and the program just freezes. I don't think it's just taking a long time to process.

What exactly did you mean by making it quadratic?

[mf]

Looks like for n=113383, the integers generated in 3n+1 sequence will overflow 32-bit integers, and this somehow leads into an infinite periodic loop.

The problem statement says "no operation overflows a 32-bit integer", so you can assume that in judge's input there will be no test cases triggering such overflows, and submit your program as is.

Or you could choose to do all computations with 64-bit integers instead.

What exactly did you mean by making it quadratic?

Time complexity.
A quadratic time algorithm would usually take many hours to complete for n=1000000.

[Anunnaki]

Looks like for n=113383, the integers generated in 3n+1 sequence will overflow 32-bit integers, and this somehow leads into an infinite periodic loop.

The problem statement says "no operation overflows a 32-bit integer", so you can assume that in judge's input there will be no test cases triggering such overflows, and submit your program as is.

Hmm, now it's telling me WA. I thought maybe it was because I actually just output the input string, instead of the integers themselves, so I changed it to output the integers--and made sure they came out in the same order as the input--but it's still giving me WA. I wonder if that has anything to do with the whole multiple line input scheme I have working in it (where you just press enter twice to get the output). I noticed some people in here just use one-line-at-a-time output in an infinite loop, when the description mentions it has to be capable of a series of integers, so I don't know.

Edit: Okay, so I changed it to one-line-at-a-time output, but now it's telling me Time Limit Exceeded. Testing on my own machine, it can do 1 to 1000000 in 1 second. Are they using some kind of ancient Pentium 1 or something? What the hell is going on?

Here's my latest code:

Code: Select all

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

int nCalc (int i, int j)
{
    unsigned long int n, a = 0;

    do
    {
            unsigned long int di = i;

            for (n = 1; di != 1; n++)
            {

                    if (n == 1)
                    {
						continue;
                    }

                    if ((di % 2) != 0)
                    {
						di = (3 * di) + 1;
						continue;
                    }

                    else
                    {
						di = di/2;
                    }

					if (n > a)
						a = n;
            }

            if (i == 1)
				n = 1;

            i++;
    }while(i <= j);

    return a;
}

int main()
{
    int n, a, b;
    vector<int> cycle, i, j, s;

        cycle.clear();

        for (int counter = 0; ; counter++)
        {
                    cin >> a >> b;

                    if (a > b)
                    {
                    	int temp = a;
                    	a = b;
                    	b = temp;
                    	s.push_back(1);
                    }

                    else s.push_back(0);

					i.push_back(a);
					j.push_back(b);

					n = nCalc(i[counter], j[counter]);

					if (s[counter] == 1)
					{
						int temp = i[counter];
						i[counter] = j[counter];
						j[counter] = temp;
					}

					cout << i[counter] << " " << j[counter] << " " << n << "\n";
        }

    return 0;
}

Edit 2: It seems if I have it in a for loop with no exit argument, it tells me Time Limit Exceeded, and if I have it in an infinite while loop, it tells me Wrong Answer. I have come to the conclusion that the Online Judge just hates me.

[mf]

Doing one case at a time is a good thing.

Testing goes like this - your program is given on its standard input (via file redirection) a file with input data, it has to run and produce a file with output data on standard output. That file is then compared with output from a reference solution. You see, it doesn't matter here whether it processes a single case at a time or all the cases at once. But doing one case at a time consumes less memory, and so is a little faster.

Try to avoid using vector<int> at all, use just int's.

Instead of cin >> a >> b and cout << x << y << z << "\n", you can use scanf("%d %d", &a, &b); and printf("%d %d %d\n", x, y, z); - they're faster.

Edit:
Oh, and don't forget to check status of input operations - you need to stop your program on end-of-file:
with iostreams: "if (!(cin >> a >> b)) break;"
with scanf: "if (scanf("%d %d", &a, &b) != 2) break;".

[Anunnaki]

Doing one case at a time is a good thing.

Testing goes like this - your program is given on its standard input (via file redirection) a file with input data, it has to run and produce a file with output data on standard output. That file is then compared with output from a reference solution. You see, it doesn't matter here whether it processes a single case at a time or all the cases at once. But doing one case at a time consumes less memory, and so is a little faster.

Try to avoid using vector<int> at all, use just int's.

Well, that's basically what I have it down to now, but it's still giving me WA. Here's the latest code:

Code: Select all

#include <iostream>

using namespace std;

int nCalc (int i, int j)
{
    unsigned long int n, a = 0;

    do
    {
            unsigned long int di = i;

            for (n = 1; di != 1; n++)
            {

                    if (n == 1)
                    {
						continue;
                    }

                    if ((di % 2) != 0)
                    {
						di = (3 * di) + 1;
						continue;
                    }

                    else
                    {
						di = di/2;
                    }

					if (n > a)
						a = n;
            }

            if (i == 1)
				n = 1;

            i++;
    }while(i <= j);

    return a;
}

int main()
{
    int n, a, b, s, counter = 0;

        while(cin >> a >> b)
        {

                    if (a > b)
                    {
                    	int temp = a;
                    	a = b;
                    	b = temp;
                    	s = 1;
                    }

                    else s = 0;

					n = nCalc(a, b);

					if (s == 1)
					{
						int temp = a;
                    	a = b;
                    	b = temp;
					}

					cout << a << " " << b << " " << n << "\n";

					counter++;

        }

    return 0;
}

Instead of cin >> a >> b and cout << x << y << z << "\n", you can use scanf("%d %d", &a, &b); and printf("%d %d %d\n", x, y, z); - they're faster.

Edit:
Oh, and don't forget to check status of input operations - you need to stop your program on end-of-file:
with iostreams: "if (!(cin >> a >> b)) break;"
with scanf: "if (scanf("%d %d", &a, &b) != 2) break;".

I don't know old-style C at all, so I don't know how to use scanf/printf. Also, how do you stop the input with "while(cin>>a>>b)"?

[mf]

For the input "1 1", the output should be "1 1 1".

[Anunnaki]

For the input "1 1", the output should be "1 1 1".

BAH! I forgot to change "n = 1" to "a = 1" when I changed the return from n to a. I knew it was something small. Thank you!

[cjrr2046]

Send this, get WA, dont know why. Works with the test cases i have found with any order (i>j and i<j)

import java.io.*;

public class Main
{
public static void main (String[] args) throws Exception
{
final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line;
line=reader.readLine ();
String[] words=line.split (" ");
int a=Integer.parseInt (words[0]);
int b=Integer.parseInt (words[1]);
if (a>b)
{
System.out.println (a+" "+b+" "+Q100.nlength (b,a));
}
else
{
System.out.println (a+" "+b+" "+Q100.nlength (a,b));
}
System.exit (0);
}
}

class Q100
{
public static int alg (int n)
{
int cont=1;
while (n>1)
{
if ((n%2)==0)
{
cont++;
n/=2;
}
else
{
cont++;
n=(3*n)+1;
}
}
return cont;
}

public static int nlength (int n1, int n2)
{
int i;
int max=0;
int aux;
for (i=n1; i<=n2; i++)
{
aux=alg(i);
if (aux>max)
{
max=aux;
}
}
return max;
}
}

[cjrr2046]

Send this, get WA, dont know why. Works with the test cases i have found with any order (i>j and i<j)

import java.io.*;

public class Main
{
public static void main (String[] args) throws Exception
{
final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String line;
line=reader.readLine ();
String[] words=line.split (" ");
int a=Integer.parseInt (words[0]);
int b=Integer.parseInt (words[1]);
if (a>b)
{
System.out.println (a+" "+b+" "+Q100.nlength (b,a));
}
else
{
System.out.println (a+" "+b+" "+Q100.nlength (a,b));
}
System.exit (0);
}
}

class Q100
{
public static int alg (int n)
{
int cont=1;
while (n>1)
{
if ((n%2)==0)
{
cont++;
n/=2;
}
else
{
cont++;
n=(3*n)+1;
}
}
return cont;
}

public static int nlength (int n1, int n2)
{
int i;
int max=0;
int aux;
for (i=n1; i<=n2; i++)
{
aux=alg(i);
if (aux>max)
{
max=aux;
}
}
return max;
}
}

[mf]

Use [code]...[/code] tags to post code.

Input file contains multiple lines with test cases, you need to process all of them, not just the first one.

[cjrr2046]

Code: Select all

import java.io.*;

public class Main
{
	public static void main (String[] args)
	{
		final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String line;
		try
		{
			while ((line=reader.readLine ())!=null)
			{
				try
				{
					String[] words=line.split (" ");
					int a=Integer.parseInt (words[0]);
					int b=Integer.parseInt (words[1]);
					if ((a>0)&&(a<1000000)&&(b>0)&&(b<1000000))
					{
						if (a>b)
						{
							System.out.println (a+" "+b+" "+Q100.nlength (b,a));
						}
						else
						{
							System.out.println (a+" "+b+" "+Q100.nlength (a,b));
						}													
					}
					else
					{
						System.out.println (a+" "+b+" "+"Error case");						
					}

				}
				catch (NumberFormatException nfe)
				{
					System.exit (0);			
				}
				catch (ArrayIndexOutOfBoundsException aioob)
				{
					System.exit (0);								
				}			
			}
		}
		catch (IOException ioe)
		{
			System.exit (0);
		}
		System.exit (0);
	}
}

class Q100
{
	public static int alg (int n)
	{
		int cont=1;
		while (n>1)
		{
		if ((n%2)==0)
		{
		cont++;
		n/=2;
		}
		else
		{
		cont++;
		n=(3*n)+1;
		}
		}
		return cont;
	}
	
	public static int nlength (int n1, int n2)
	{
		int i;
		int max=0;
		int aux;
		for (i=n1; i<=n2; i++)
		{
		aux=alg(i);
		if (aux>max)
		{
		max=aux;
		}
		}
		return max;
	}
}

Send this, process multiple test cases, still get WA. Works with the test cases i have found with any order (i>j and i<j). Also handles exceptions for some test cases (like just getting 1 number as input).

[mf]

I think the numbers on each line may be separated by more than one space, and there could be leading/trailing whitespaces. In that case, this part of your code won't work:

Code: Select all

String[] words=line.split (" ");
int a=Integer.parseInt (words[0]);
int b=Integer.parseInt (words[1]);

You can use java.util.StringTokenizer to deal with all extra whitespace.

Also handles exceptions for some test cases (like just getting 1 number as input).

Actually you don't need to do that. An uncaught exception (or System.exit(n), with n != 0) will be reported to you as a 'Runtime Error', but if you try to catch it and terminate your program with System.exit(0), judge will think that your program terminated normally, and you'll only get WA.

[brock]

//i dont get y am i getting a wrong answer in this code
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int max(int a,int b){
if(a>b)
return a;
else
return b;
}
int main(){
int n,i=0,j,n1,t,f,l,temp=1,check=0;

while(cin>>f>>l){
if(f>l){
check=1;
swap(f,l);
}
temp=1;
for(n=f;n<=l;n++){
i=0;
n1=n;
while(1){
w:
i++;
if(n1==1){
break;
}
else if(n1%2==1){
n1=3*n1+1;
}
else{
n1=n1/2;
}
goto w;
}
//cout<<i<<endl;
if(n==f){
temp=i;
}else{
temp=max(i,temp);
}
}
if(check==0)
cout<<f<<" "<<l<<" "<<temp<<endl;
if(check==1){
swap(f,l);
cout<<f<<" "<<l<<" "<<temp<<endl;
}
t--;
}
return 0;
}