Challenge: faster 3n+1 solution

[anup30]

Make your code as fast as possible:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

The Problem

Consider the following algorithm:
1. input n

2. print n

3. if n = 1 then STOP

4. if n is odd then n= 3*n+1;

5. else n= n/2;

6. GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input
The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output
For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).


Sample Input

1 1
1 10
100 200
210 201
900 1000

Sample Output

1 1 1
1 10 20
100 200 125
210 201 89
900 1000 174

[anup30]

run time: 0.952 sec

// UVa online judge, problem 100, The 3n + 1 problem
#include <iostream>
using namespace std;

int main ()
{
	unsigned int i,j, cl, mcl;	
	while(cin >> i >> j){
		unsigned int i2, j2;
		i2 = i<=j ? i:j;
		j2 = i<=j ? j:i; 
		cl=0;
		mcl=0;		
		for(int k=i2; k<=j2; k++)
		{
			cl=0;
			int k2=k;			
			while(k2 !=1 )
			{
				if(k2%2 ==1) { k2 = k2*3 +1; cl++;	}
				else { k2 /= 2;	cl++;	}
			}
			cl++;
			if(cl>mcl) mcl =cl;
		}		
		cout << i << " " << j << " " << mcl << "\n";
	}
	
return 0;	
}

[MiiNiPaa]

Fastest solution would be statically declaring an array containing lengths of sequences starting from 1 to 1000000 and then just making O(n) pass on it for each pair.
(actual fastest solution would be using 2D table for O(1) lookup, but it would require more than 1 TB of memory).

As bonus: compile-time generation of such array. Size of generated array is constrained due to sanity reasons (and because of fear for the compiler).

#include <algorithm>
#include <iostream>

template<unsigned i> struct sequence
{ static const unsigned size = sequence<( i%2 ? 3*i+1 : i/2 )>::size + 1; };

template<  /* 1 */ > struct sequence<1>
{ static const unsigned size = 1; };


template<unsigned ... values> struct holder
{ static const unsigned  arr[sizeof...(values)]; };
template<unsigned ... values> const unsigned  holder<values...>::arr[sizeof...(values)] = {values...};


template<unsigned n, unsigned ...values> struct filler : filler<n-1, sequence<n>::size, values...> {};
template<    /* 0 */ unsigned ...values> struct filler<0, values...> : holder<0, values...> {};

int main()
{
    const unsigned * array = filler<888>::arr;

    std::cin.sync_with_stdio(false);
    int s, e;
    while(std::cin >> s >> e)
        std::cout << s << ' ' << e << ' ' <<
                     *std::max_element(array+std::min(s, e), array+std::max(s, e)+1) << '\n';
}

EDIT:

unsigned int

ah, I see, you encountered great number 113383.

[LB]

@MiiNiPaa: although insane, would it not be faster to have the output already present in string form so that the numbers don't need to be converted to strings?

[MiiNiPaa]

That would add another 8-12 (depending on pointer size) MB to the executable size and used memory. More memory if we use std:string. I believe that IO speed itself would play greater role than calculations.

[ne555]

> making O(n) pass on it for each pair.
it can be better
http://en.wikipedia.org/wiki/Range_minimum_query
(the one with O(n lg n) space is not so hard to code)

[anup30]

@MiiNiPaa: wrong output for

900 1000

[MiiNiPaa]

Did you change array size to include both 900 and 1000?

MiiNiPaa wrote:

Size of generated array is constrained due to sanity reasons

MiiNiPaa wrote:

const unsigned * array = filler<888>::arr;

Variant without compile-time magic:

#include <algorithm>
#include <iostream>

#include "huge_array.h"

int main()
{
    std::cin.sync_with_stdio(false);
    int s, e;
    while(std::cin >> s >> e)
        std::cout << s << ' ' << e << ' ' <<
                     *std::max_element(array+std::min(s, e), array+std::max(s, e)+1) << '\n';
}

Contents of huge_array.h: https://justpaste.it/k6we

[anup30]

there are some things in your code which i didn't learn yet.
how to edit your code to work for 1 999999 (lower and upper limit of the problem) ?

[MiiNiPaa]

change 888 in filler<888>::arr; to other number. Note that it is not recommended unless you have a supercomputer. Compilation of 1 00 000 array for me hanged after allocating 12 GB of memory. Most likely compiler will not let you do it and you will have to disable safety yourself.
Therefore "Size of generated array is constrained due to sanity reasons".

Use second boring code with array already generated for you.

[anup30]

so it can't be submitted in UVa ?

[MiiNiPaa]

I do not know. It depends on what they allow. First code would almost certainly be rejected (although it is valid C++ code and works correctly) due to compiler constraints.

Second code should be approved unless they have some restrictions on file size (it will be arount 4.5 MB)

[ne555]

If you can't have the array generated at compile-time, then generate it at run-time.
The idea is to avoid to recalculate the length of the cycle for all the numbers in the range, just do it one time, store the result and then perform a range maximum query (which, I insist, it can be done better than O(n) of std::max_element)

[MiiNiPaa]

As it is completely possible that not all numbers in range are going to be tested, you can generate only those numbers you need: allocate arrray and initialze it with 0. When you need number, check if corresponding array element is 0. If it is, generate number and store it there. Then just take value. Try both "generate all at once" and "generate on demand" approaches and select which will be fastest on used series of tests.

[LB]

@MiiNiPaa: that's called memo-ization, right? That's what my professors call it.

[anup30]

36 millisecond

// UVa online judge, problem 100, The 3n + 1 problem 
// run time 0.036 sec

#include <iostream>
using namespace std;

int main (){
	typedef unsigned int ui; 
	ui *ar = new ui[1000001] {0,1,2};
	ui cl;
	
	for(ui i=3; i<1000001; i++){
		cl=0;
		ui j=i;
		while(j != 1){			
			if(j%2==1) { j= (3*j+1)/2; cl+=2;  }
			else { j /= 2; cl++;  }
			if(j<i) { cl += ar[j]; break;  }
		}
		ar[i] = cl;	
	}
		
	ui x,y;
	while(cin >> x >> y){
		cout << x << " " << y << " ";
		if(x>y) std::swap(x,y);
		ui max = ar[y];
		for(ui i=y-1; i>=x; i--){
			if(ar[i]>max) max=ar[i];
		}
		cout << max << "\n";
	}	
	
// delete[] ar;
return 0;	
}