I’ve written a solution for “The 3n+1 problem”, the first task in the Universidad de Valladolid programming contest.
My weapon of choice was C. I’ve got a ranking beneath the first 550 contestants with a cpu time of 0.084 and ‘minimal’ memory usage.
I tried different technologies:
- full blown hash tables
- simple caching per direct adressing
- iterative implementation
- recursive implementation
- precalculated values
My fastest solution uses a recursive implementation and a direct addressing cache. Precalculated values suprisingly caused a performance drop.
The guys on the first ranks have cpu times of 0.000 and ‘minimal’ memory usage. I’m very interested in how this is done. If you have a faster solution, please comment or write me! Or feel free to improve my code.
Also, there may be some mathematical tricks, I don’t know.
Here’s the code:
#include <stdio.h> #define SIZE 1000001 static unsigned short table[SIZE]; unsigned short calcCycleLength( register unsigned long n ) { if(n < SIZE && table[n]) return table[n]; if(n & 1){ /* if n is odd */ if( n < SIZE) { table[n] = 2 + calcCycleLength( (3*n+1) >> 1 ); /* calc two steps at one */ return table[n]; } else return 2 + calcCycleLength( (3*n+1) >> 1 ); } else { if( n < SIZE) { table[n] = 1 + calcCycleLength( n >> 1 ); /* n/2 */ return table[n]; } else return 1 + calcCycleLength( n >> 1 ); } } int main() { unsigned long i, fstIn, sndIn; short out = 0, temp; table[1] = 1; while ( scanf("%lu %lu", &fstIn, &sndIn ) != EOF ) { if( fstIn > sndIn) { for( i = sndIn; i <= fstIn; ++i ) { temp = calcCycleLength( i ); if( temp > out) out = temp; } } else { for( i = fstIn; i <= sndIn; ++i ) { temp = calcCycleLength( i ); if( temp > out) out = temp; } } printf("%lu %lu %hdn", fstIn, sndIn, out); out = 0; } return 0; }
When thinking about this problem, I thought how I would solve it in haskell. I came up with the following one-liner:
(maximum . map ((+1) . length . takeWhile (/=1) . iterate (\n -> if n `mod` 2 == 0 then n `div` 2 else 3*n+1) ) . uncurry enumFromTo)
This takes a pair (the range) and gives the right answer. Looks like haskell is to such problems what perl is to system administration.
(I’m not claiming that is’s fast, though. Just fast to write.)
Just a thought: Might it be faster to make your recursive function tail-recursive, or just wrap it in a while loop?
Hmm. Probably not possible, as you also write the results to the table. Nevermind 🙂
I’ve tried a complete iterative solution (the while loop), and also a tail-recursive one by implementing the n/2 in a while loop and recursing only the ‘odd’ part. Both solutions were significantly slower than this one.
The full hashtable performed somewhat slower. I used a bad hash function (x mod n), which wasn’t uniformley distributed. Furthermore, the malloc calls costs some performance.
So, getting rid of the malloc (perhaps with alloca or a complete preallocation) and inventing a better hash function could boost the performance.
something similar in c++…
#include
using namespace std;
const unsigned long int MAX=1000000;
unsigned long int lengths[MAX];
unsigned long int clength(unsigned long int inp);
int main()
{
unsigned long int a,b;
while (cin>>a>>b)
{
unsigned long int cycleLength=0, maxLength=0;
for(unsigned long int i=a;imaxLength)
maxLength=cycleLength;
}
cout>1);
else
lengths[inp] = 2 + clength((3*inp + 1)>>1);
return lengths[inp];
}
I was looking around to see who has solved this, I get the right answers on my PC based on 110101.inp but when I submit it online, the judge system keeps telling me wrong answer. Any ideas why? It’s in C++.
#include
#include
using namespace std;
int main(int argc, char **argv) {
int first = 0, last = 0, maxCycleLength = 0;
while(cin >> first >> last) {
if ( first > last ) {
int temp = first;
first = last;
last = temp;
}
maxCycleLength = 0;
for (int x = first; x maxCycleLength)
maxCycleLength = cycleLength;
}
cout << first << ” ” << last << ” ” << maxCycleLength << “\n”;
}
exit(0);
}
BTW, I submitted this to programming-challenges.com website.
Niraj
I figured it out, when I swapped the inputs if first was larger than the other, I printed them in swapped output.
Niraj
Hi Niraj!
Thank you for your comments. How fast is your solution?
Tante, the time was 6.328 secs, pretty slow. I needed to get it working first. Reading this thread, I realized type of changes I need to make to make it more optimal solution, such as caching data, hopefully without running out of memory.
Niraj
By using C++ map objects to cache, the time came down slightly to 4.688 secs.
Hm, the version I posted runs in 0.084 secs …
fantastic!!!!!
try this too: cycle of power nth of n is n+1
or if you init 10 or 20 elements of your table, maybe make it faster
:-??
i submitted this program, and it has wrong answer:
i adapted u in using bitwise operators :p
#include
int main(void)
{
unsigned long i,j;
while(scanf(“%lu %lu”,&i,&j)!= EOF)
{
short max=0;
register int loop;
if(i>j)
{
unsigned long temp=i;
i=j;
i = temp;
}
for( loop = i;loop>1);
}
max = (max>il)?max:il;
}
printf(“%lu %lu %hd\n”,i,j,max);
}
return 0;
}
#include
int main(void)
{
unsigned long i,j;
while(scanf(“%lu %lu”,&i,&j)!= EOF)
{
short max=0;
register int loop;
if(i>j)
{
unsigned long temp=i;
i=j;
i = temp;
}
for( loop = i;loop>1);
}
max = (max>il)?max:il;
}
printf(“%lu %lu %hd\n”,i,j,max);
}
return 0;
}
for( loop = i;loop>1);
}
I tackled the problem in the same way you did, though I used C++, I first tried pre-calculated values and then I settled on filling in the max cycles for other values as I came across them while I was calculating the current max cycle value… I believe this is right on par with you… Anyway the code is tightened up a bit more and I created less array elements on the magnitude of 10 than your example and with it I recieved an Accepted Verdict with a runtime of 0.030. Here’s the code…
#include
#define SIZE 100001
static unsigned short table[SIZE];
unsigned short FindMaxCycle(register unsigned int n)
{
if(n > 1);
else table[n] = 1 + FindMaxCycle(n >> 1);
return table[n];
}
if(n & 1) return 2 + FindMaxCycle((3 * n + 1) >> 1);
return 1 + FindMaxCycle(n >> 1);
}
int main()
{
unsigned int i, j;
unsigned short hCnt, cnt;
table[1] = 1;
while(std::cin >> i >> j)
{
hCnt = 1;
std::cout << i << ” ” << j < j)
{
for( ; j hCnt) hCnt = cnt;
}
}
else
{
for( ; i hCnt) hCnt = cnt;
}
}
std::cout << hCnt << std::endl;
}
}
Anyway I still think that there is something I am missing, I don’t know if I am spending too much time calculating unecessary values that won’t be used on future calculations. Also I agree with you that there may be a potential mathimatical algorithm that can estimate the values without a recursive calculation, but these are just thougts, I would love to see some more examples with the running time posted.
Thanx,
Jay
Thanks Jay! Interesting stuff!
I’m not working on this problem any more (at the moment…). But I have some half-baked stuff not posted yet:
There’s a nice site with “bit hacks” (http://graphics.stanford.edu/~seander/bithacks.html). Maybe, one can use one of these to short circuit the bit shifts. Especially the deBruijn method to find the log base 2 of an N-bit integer looks promising.
If you plot the input integer against the corresponding cycle length, you will notice some sort of a noisy pattern. In general, such a pattern stands for hidden information. So I trained a neural network to estimate the probability distribution for a given integer to result in a specific cycle length. Don’t no how to use this yet. Maybe consider a “probabilistic” solution throwing away the less probable cycle lengthes etc.
I’ve also tried “cheating”. Waiting some seconds and then dividing by zero can be used to extract information out of the judge. The judge seems to use many, many input pairs with small intervalls. No investigated any further.
Furthermore to calculate EVERY thinkable input, you have to use 64bit arithmetic. Since the judge also accepets the faulty 32bit solution, it doesn’t use these dangerous inputs. This gives us information about the maximum interval between the two input integers (it nevers spans across one of the bad values).
Here is my solution in Common Lisp. No memoization, no type declarations, no compiler optimization hacks; just a tail recursive function implementation.
(defun cycle-length (n &optional (l 1))
(if (< 1 n)
(cycle-length (if (oddp n) (1+ (* 3 n)) (/ n 2)) (1+ l))
l))
(defun maximum-cycle-length (i j &optional (l 0))
(if (< i j)
(maximum-cycle-length i (1- j) (max l (cycle-length j)))
l))
(time
(loop for (i j) in ‘((1 10) (100 200) (201 210) (900 1000))
collect (maximum-cycle-length i j)))
Evaluation took:
0.002 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
0.00% CPU
1,689,109 processor cycles
0 bytes consed
(20 125 89 174)
I submitted your solution to the online judge and got the verdict wrong answer.
The Common Lisp guy doesn’t realize that the judge will run the program on a larger set of numbers, thus vastly increasing the run time. Try 1…999999 instead.
when ever I submitted this problem…
I got wrong ans…
cn any one help me to get rid of the porb…
plssssssssssssssss…
#include
unsigned short length(unsigned long n);
int main()
{
unsigned long i,a,b,x,y;
int max = 0;
int temp = 0;
while(scanf(“%lu %lu”,&a,&b)==2)
{
x = a;
y = b;
if(a > b)
{
a = y;
b = x;
}
for(i = a;imax)
{
max = temp;
}
}
printf(“%lu %lu %d\n”,a,b,max);
max = 0;
}
return 0;
}
int length(unsigned long n)
{
int len = 1;
while(n!=1)
{
if(n%2==1)
{
n = 3*n + 1;
}
else
{
n = n/2;
}
len++;
}
return len;
}
#include
unsigned short length(unsigned long n);
int main()
{
unsigned long i,a,b,x,y;
int max = 0;
int temp = 0;
while(scanf(“%lu %lu”,&a,&b)==2)
{
x = a;
y = b;
if(a > b)
{
a = y;
b = x;
}
for(i = a;imax)
{
max = temp;
}
}
printf(“%lu %lu %d\n”,a,b,max);
max = 0;
}
return 0;
}
int length(unsigned long n)
{
int len = 1;
while(n!=1)
{
if(n%2==1)
{
n = 3*n + 1;
}
else
{
n = n/2;
}
len++;
}
return len;
}
It is a good solution:
#include
#include
using namespace std;
long cycleLen(unsigned long n)
{
int len=1;
while(n!=1)
{
if(n%2==1)
{
n=3*n+1;
}
else
{
n=n/2;
}
len=len+1;
}
return len;
}
void swap(unsigned long& i, unsigned long& j)
{
unsigned long tmp=0;
tmp=i;
i=j;
j=tmp;
}
int main()
{
unsigned long i=0,oldi=0;
unsigned long j=0,oldj=0;
unsigned long max=0;
unsigned long tmp=0;
while(cin>>i && cin>>j)
{
oldi=i;
oldj=j;
if(i>j)
{
swap(i,j);
}
for(unsigned long p=i;p<=j;p++)
{
tmp=cycleLen(p);
if(max<tmp)
{
max=tmp;
}
}
cout<<oldi<<" "<<oldj<<" "<<max<<"\n";
max=0;
}
return 0;
}
if input is
10 1
output should be
1 10 20
🙂
hello
i submit this program but i get (Time limit exceeded) error.
my program run in 3.000 sec.
Pleas help me to correct that.
my code:
#include “iostream”
using namespace std;
int main(){
unsigned int inI,
inJ;
int counter,MaxCounter;
do{
MaxCounter=0;
cin>>inI>>inJ;
cout<<inI<<" "<<inJ<1){
curpos=(curpos%2)?(3*curpos)+1:curpos/2;
counter++;
}
if (counter>MaxCounter) MaxCounter=counter;
inI++;
}while(inI<=inJ);
cout<<MaxCounter<<"\n";
}while(inI);
return 0;
}
how can I use this code but in Java???
#include
int main (int argc, char *argv[])
{
int i, j, ii, n, size, max;
while (scanf (“%d %d”, &i, &j) == 2)
{
ii = i;
max = 0;
for (i; i 1)
{
size++;
if (n%2 == 0)
n = n/2;
else
n = 3*n + 1;
}
if (size > max)
max = size;
}
printf (“%d %d %d\n”, ii, j, max);
}
}
This is the fastest one I can get:
Run Time: 0.020
#include
#define MAX(x, y) (x) > (y) ? (x) : (y)
#define SWAP(a, b) {a ^= b; b ^= a; a ^= b;}
#define SIZE 1000000
static unsigned table[SIZE];
unsigned _get_cycle_len(unsigned n, unsigned *cycle_len_counter)
{
if (n 1)
{
if (n & 1)
{
n = 3 * n + 1;
}
else
{
n >>= 1;
}
if (n j)
{
SWAP(i, j);
}
while (i max)
{
max = table[i];
}
}
else
{
*cycle_len_counter = 0; // Must initialize to zero.
table[i] = _get_cycle_len(i, cycle_len_counter); // Get the cycle length of the number.
if (table[i] > max)
{
max = table[i];
}
}
//printf(“table[%u]: %u\n”, i, table[i]);
i++;
}
return max;
}
int main(void)
{
unsigned i = 0, j = 0;
// ### Use this block to Find the max cycle length in a range of number.
while(scanf(“%u %u”, &i, &j) != EOF)
{
printf(“%u %u %u\n”, i, j, _get_max_cycle_len(i, j));
}
// ### Use this block to see one number only.
//while(scanf(“%u”, &i) != EOF)
//{
//*cycle_len_counter = 0;
//table[i] = _get_cycle_len(i, cycle_len_counter);
//printf(“table[%u] = %u\n”, i, table[i]);
//printf(“\n”);
//}
return 0;
}
I’ve done this problem a lot of times but i continue getting “wrong answer”, but when i test it the answers are ok… i need help please…
this is the code in c++ :
#include
#include
#include
using namespace std;
int funcion(int nu){
int cont = 1;
while(nu != 1){
if(nu % 2 == 0){
nu = nu/2;
cont++;
}
else if(nu % 2 != 0){
nu = 3*nu + 1;
cont++;
}
}
return cont;
}
int rango(int i, int j){
list li;
for(int k = i; k >i>>j){
cout<<i<<" "<<j<<" "<<rango(i,j)<<endl;
}
return (EXIT_SUCCESS);
}
anyone have a correct solution in java? I think my input/output is wrong 😦
mine solution:
class myStuf implements Runnable{
public void run(){
String s = Main.ReadLn(9999);
while( s != null && !s.trim().equals(“”) ){
if( !s.equals(“\n”)){
String[] tmp = s.replace(‘\n’,’ ‘).trim().split(” “) ;
int a = Integer.parseInt(tmp[0]) ;
int b = Integer.parseInt(tmp[1]) ;
if( a > b)
System.out.print( a + ” ” + b + ” ” + getMax( b, a) + “\n” );
else
System.out.print( a + ” ” + b + ” ” + getMax( a,b ) + “\n”);
s = Main.ReadLn(9999);
}
}
}
public int getMax( int a, int b){
int max = 0 ;
for( int i = a ; i <= b ; i++ ){
int t = lengte( i ) ;
if( max < t )
max = t ;
}
return max ;
}
public int lengte( int n ){
int aantal = 1 ;
while( n != 1 ){
aantal++ ;
if( n % 2 == 0 ){
n /= 2 ;
}else
n = n *3 + 1 ;
}
return aantal ;
}
}
(using the javainput file like on the website)
You could translate 3*n + 1 to ((n << 1) | 1) + n
Hi.
in pdf file talked about all integers are less than 10000 but in website that is 1000,000!!! so i think zero time is for solving problem with small range. if n<10000 we can save all cycle in source code!!! (it will be less than 40k) and answer calculate with a little search!!.
with shifting and register and all optimal works program can not be zero.
#include
using namespace std;
int calc(unsigned long , unsigned long);
int main()
{
unsigned long i,j;
while(cin>>i>>j)
{
calc(i,j);
}
return 0;
}
int calc(unsigned long i, unsigned long j)
{
unsigned long num, count, i_i, max_count,temp=0;
max_count=1;
count=1;
if(j<i)
{
temp=i;
i=j;
j=temp;
temp=1;
}
for(i_i=i; i<=j; i++)
{
count=1;
num=i;
do{
if(num==1)
break;
count++;
if((num%2) != 0)
{
num= (num*3)+1;
}
else if(num%2==0)
{
num=num/2;
}
if(max_count<count)
{
max_count=count;
}
}while(num!=1);
}
if(temp==0)
cout<<i_i<<" "<<j<<" "<<max_count<<endl;
if(temp==1)
cout<<j<<" "<<i_i<<" "<<max_count<<endl;
return 0;
}
0.628 seconds
pretty simple, but the best ones have a runtime of 0.000sec.
How??
I’m sure that my code work properly in my PC but when I submit it to the server why I got false results, help me please!!
โครตยาก
i have submitted this code on judge but it gives me exceeds time error .. can any one help me please :
//c++ code
#include
#include
#include
using namespace std;
int main(){
int num1,num2,counter=1,s=0,x=0;
while(true){
x=0,s=0;
cin>>num1>>num2;
if(num1>num2){
for(int i=num1;i>=num2;i–){
x=i;
while(true){
asd:
if(x==1)break;
if(x%2==1)x=((x*3)+1);
else x=x/2;
counter++;
goto asd;
}
if(counter>s)s=counter;
counter=1;
}
}
//——————————————-
else{
for(int i=num2;i>=num1;i–){
x=i;
while(true){
ase:
if(x==1)break;
if(x%2==1)x=((x*3)+1);
else x=x/2;
counter++;
goto ase;
}
if(counter>s)s=counter;
counter=1;
}
}
//—————————————————–
cout<<num1<<" "<<num2<<" "<<s<<endl;
}
return 0;
}
thnx in advance 🙂
to suceed a better algorith solution do this:
keep the values you solute…
an example…
circle(7):22 14 34 17 52 26 13 40 20 10 5 16 8 4 2 1
cicle(7):17 moves
circle(22):16 moves
circle(14):15 moves
circle(34):14 moves
circle(17)13 moves
circle(52):12 moves
etc… (so you have those solutions in O(n)[because of research] instead of O(N^2)
my simple solution
#include
using namespace std;
int calc() {
int i,cur,max,a,a1,pos;
cin>>a;
cin>>a1;
cur=0;
for (i=a+1;i<a1;i++) {
max=1;
pos=i;
while (pos!=1) {
if (pos % 2==1) {
pos=3*pos+1;
max++;
}
else {
pos=pos/2;
max++;
}
}
if (cur<max)
cur=max;
}
cout<<a<<" "<<a1<<" "<<cur<<endl;
return 0;
}
int main () {
calc();
return 0;
}
(it sais me wrong but i dont think so!)
Hi friends,
I am a bit bewildered to know why is my submission wrong. Can someone point out the flaw. Its java submission
/*
* Main.java
* java program model for http://www.programming-challenges.com
*/
import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeMap;
import java.lang.NumberFormatException;
import java.util.HashMap;
import java.util.Map;
import java.io.IOException;
class Main implements Runnable {
/**
* 1. good policy is to read a file as quickly as possible and not keep the reader alive for long
* 2. make a map .. look further to keep it more smart
*/
static String ReadLn(int maxLength){ // utility function to read from stdin,
// Provided by Programming-challenges, edit for style only
byte line[] = new byte [maxLength];
int length = 0;
int input = -1;
try{
while (length < maxLength){//Read untill maxlength
input = System.in.read();
if ((input < 0) || (input == '\n')) break; //or untill end of line ninput
line [length++] += input;
}
if ((input < 0) && (length == 0)) return null; // eof
return new String(line, 0, length);
}catch (IOException e){
return null;
}
}
void perform(){
ArrayList inputList = new ArrayList();
TreeMap results = new TreeMap();
ArrayList outputList = new ArrayList();
String string = null;
do{
string = ReadLn(100);
if(string != null && string.length()>0)
inputList.add(string);
}while(string!=null && string.length()>0);
results.put(0,0);
results.put(1,1);
for(Iterator it = inputList.iterator(); it.hasNext();){
String str = it.next();
try{
String[] tmp = str.split(“\\s”);
int[] values = new int[2];
values[0] = Integer.parseInt(tmp[0].trim());
values[1] = Integer.parseInt(tmp[1].trim());
if(values[0] > values[1]){
values[0] = values[0] ^ values[1];
values[1] = values[0] ^ values[1];
values[0] = values[0] ^ values[1];
}
int max = 0;
for(int i = values[0]; i<=values[1]; i++){
HashMap tempValues = new HashMap();
int j = i, count = 1;
if(!results.containsKey(i)){
while(j!=1){
if(j%2==1)
j=3*j+1;
else
j/=2;
if(results.containsKey(j)){
count+=results.get(j);
j=1;
break;
}
else
tempValues.put(j,count);
count++;
}
results.put(i,count);
Iterator<Map.Entry> it2 = tempValues.entrySet().iterator();
while(it2.hasNext()){
Map.Entry tmpVal = it2.next();
results.put(tmpVal.getKey(),count – tmpVal.getValue());
}
}
max = (count>max)?count:max;
}
outputList.add(str + ” ” + String.valueOf(max));
}
catch(NumberFormatException e){
e.printStackTrace();
}
}
for(Iterator it = outputList.iterator(); it.hasNext();)
System.out.println(it.next());
}
public static void main(String args[]){
Main myWork = new Main();
myWork.run();
}
public void run(){
perform();
}
}
Please help..
I have made the program running yet i get a “WRONG ANSWER” when I submit.
It takes the foll input
./a.out
Here is my source code. It is a naive approach. Im learning how to submit n get the program working.
/*@BEGIN SOURCE CODE*/
#include
#include
#include
#include
#include
using namespace std;
int main(int argc, char *argv[] ) {
long i,j,k;
unsigned counter = 1;
char buffer[50];
char *tmp;
fstream filePointer, outputFilePointer;
if(argc != 3){
cout << "Usage: 3n+1 ” << endl;
return 1;
}
char *input_file = argv[1];
filePointer.open( input_file, ios::in );
if(!filePointer.is_open( )) {
cerr << "Failed to open file" << endl;
return 1;
}
char* output_file = argv[2];
outputFilePointer.open(output_file, ios::out );
if(!outputFilePointer.is_open( )) {
cerr << "Failed to create output file" < 0 & j > 0) & (j > i)) {
outputFilePointer << i;
outputFilePointer << " " < max )
max = counter;
counter = 1;
k–;
j = k;
}
outputFilePointer << " " << max << "\n";
}
}
/*@END SOURCE CODE*/
P.S. Any help would be appreciated
i want fractal image for3x+1.
I have try my best to optimize my code and alg, but I still can’t reach the goal – “0.000” seconds.
Originally, I use variable length array to store the steps to make sure no repeat caculations, But I got a runtime error. This is my original code.
#include
#include
int *array;
int *temp;
int array_len = 0;
int temp_len;
int stack[100000];
int p = -1;
int f(int n){
if( n % 2 == 0 ) return n/2;
else return (n * 3 + 1) ;
}
int max(int a, int b){
if(a >= b) return a;
else return b;
}
int min(int a, int b){
if(a array_len){
temp_len = 3*x+1;
temp_len = min(2147483647, temp_len);
temp = (int *)realloc(array, (temp_len + 1) * sizeof(int));
/*printf(“do realloc from %d to %d\n”, array_len, temp_len);*/
if(NULL!=temp){
/*set newly allocated memory to zero. */
memset(temp + array_len + 1, 0, sizeof(int) * (temp_len – array_len));
array_len = temp_len;
array = temp;
}else{
printf(“error!”);
exit(0);
}
}
if( array_len >= x && array[x]!=0 ) {
/* printf(“existing cycle of %d is %d\n”, x, array[x]); */
return array[x];
}else{
array[x] = cycle_length(f(x)) + 1;
/* printf(“caculate cycle of %d is %d\n”, x, array[x]); */
return array[x];
}
}
int check_array(int x)
{
/*init*/
if(array == NULL){
array_len = 3*x + 1;
array_len = min(2147483647, array_len);
array = (int *)calloc( array_len + 1, sizeof(int));
array[1] = 1;
}else if(x > array_len){
temp_len = 3*x+1;
temp_len = min(2147483647, temp_len);
temp = (int *)realloc(array, (temp_len + 1) * sizeof(int));
/*printf(“do realloc from %d to %d\n”, array_len, temp_len);*/
if(NULL!=temp){
/*set newly allocated memory to zero. */
memset(temp + array_len + 1, 0, sizeof(int) * (temp_len – array_len));
array_len = temp_len;
array = temp;
}else{
printf(“error!”);
exit(0);
}
}
}
int cycle_length2(int x){
check_array(x);
if( array_len >= x && array[x]!=0 ) {
/* printf(“existing cycle of %d is %d\n”, x, array[x]); */
return array[x];
}
int c,k;
p = -1;
stack[++p] = x ;
while(p>=0){
c = stack[p];
k = f(c);
/*printf(“k=%d\n”, k);*/
if( array_len >= k && array[k]!=0 ){
check_array(c);
array[c] = array[k] + 1;
p–;
}else{
stack[++p] = k;
}
}
return array[x];
}
int
main(void)
{
int i, j, k, cycle, max_cycle_sofar;
while( scanf(“%d %d”, &i, &j)!=EOF ){
/*printf(“%d %d\n”, i,j );*/
cycle = 0;
max_cycle_sofar = 0;
for(k=j; k>=i; k–){
cycle = cycle_length2(k);
if( cycle==0 ){
printf(“fuck me!\n”);
}
/* printf(“cycle of %d is: %d\n”, k, cycle); */
max_cycle_sofar = max( cycle, max_cycle_sofar);
}
printf(“%d %d %d\n”, i, j, max_cycle_sofar);
}
return 0;
}
When I read your code, then I reallized that I don’t need to store every step of n. So come’s to me second solution.
#include
#include
#define MAX_ARRAY_LEN 1000001
#define MAX_STACK_LEN 100000
unsigned short array[MAX_ARRAY_LEN+1];
unsigned long int stack[MAX_STACK_LEN+1];
int sp;
unsigned long int f(unsigned long int n){
if( n & 1 ) return (n * 3 + 1) ;
else return n/2;
}
unsigned short int max(unsigned short int a, unsigned short int b){
if(a >= b) return a;
else return b;
}
int cycle_length(int x){
unsigned long int c, fc;
unsigned short val;
if( MAX_ARRAY_LEN >= x && array[x]!=0 ) {
return array[x];
}
sp = -1;
val = 0 ;
stack[++sp] = x;
while(sp>=0){
c = stack[sp];
fc = f(c);
if( MAX_ARRAY_LEN >= fc && array[fc]!=0 ){
val = array[fc] + 1;
if( MAX_ARRAY_LEN >= c ) array[c] = val;
sp–;
}else if(val != 0){
val++ ;
if( MAX_ARRAY_LEN >= c ) array[c] = val;
sp–;
}else{
stack[++sp] = fc;
}
}
return val;
}
int
main(void)
{
unsigned short cycle, max_cycle_sofar;
unsigned long i, j, k;
array[1] = 1;
while( scanf(“%lu %lu”, &i, &j)!=EOF ){
cycle = 0;
max_cycle_sofar = 0;
if(i =i; k–){
cycle = cycle_length(k);
max_cycle_sofar = max( cycle, max_cycle_sofar);
}
}else{
for(k=i; k>=j; k–){
cycle = cycle_length(k);
max_cycle_sofar = max( cycle, max_cycle_sofar);
}
}
printf(“%lu %lu %d\n”, i, j, max_cycle_sofar);
}
return 0;
}
I didn’t use recursion to save some time, but is still take at least 0.020 seconds.
So, I give up the thought of optimizing the code. Maybe there is a math solotion for this. How about you?
Hello Everyone, My code is compiling on my PC, I am using Microsoft Visual Studio 2008, but for some reason, the judge tells me I am having a Compilation error.
I think it might be cause of
int _tmain(int argc, _TCHAR* argv[])
or the imports, but I am not sure, so here is my entire code, why will this only compile on my machine and not on the judges.
————————————————————————————————————————————————————————————————————————————————
#include “stdafx.h”
#include
using namespace std;
int CalculateSteps(int number, int steps)
{
if(number == 1)
{
return steps;
}
else if( number % 2 == 1)
{
number = (number * 3) + 1;
}
else
{
number /= 2;
}
steps++;
return CalculateSteps(number, steps);
}
int _tmain(int argc, _TCHAR* argv[])
{
int num, max, a, b;
while (cin>>a>>b)
{
max = 0;
for(int i = a; i max)
{
max = num;
}
}
cout<< a << " " << b << " " << max << endl;
}
return 0;
}
pretty short and standard solution with 0.735 sec
#include
#include
using namespace std;
int calcCycleLength(int num) {
int count = 1;
while (num > 1) {
if (num % 2) {
num = num * 3 + 1;
} else {
num /= 2;
}
++count;
}
return count;
}
int main()
{
string input;
while (getline(cin, input)) {
istringstream is(input);
int i, j;
is >> i;
is >> j;
bool swapped = (i > j);
int num = (swapped ? j : i);
int end = (swapped ? i : j);
int maxLength = 0;
while (num <= end) {
int cycleLength = calcCycleLength(num);
if (maxLength < cycleLength) {
maxLength = cycleLength;
}
++num;
}
cout << i << " " << j << " " << maxLength << endl;
}
return 0;
}
With little modification, Even your algorithm is running in 0 time..
Would be really cool, if you could tell us that little modification… 🙂
Fine tuning it… following output for chache 30750 instead SIZE 1000001
$ ./hailstone
1 100000
Approx Execution time:0
1 100000 351
Hi ,
I did the following optimization –
A. Use pre-computed chache of cycle length for first 127 odd elements 257 generated during the computation of cycle length
C. Now perform the below three operation
HSS_CYCLE_LEN len, num
* Repeat FOREVER
* a. len := no. of trailing zeros // n/2
* b. num >>= len
* c. key :- num >> 1 // Num will be always odd here afterwards
* d. if key < chache_size && chache[key] != 0 // num in chache no need to compute
* len += chache[key]
* break;
* e. else
* ####record this intermediate num and len
* len++;
* num = num << 1 + num + 1;
* f. update Hash with ####
* return len;
Optimizations –
1. Algorithm is iterative
2. Bitwise operations are performed
3. N/2 computation loop is eliminated
4. Only odd numbers are chached, No need to chache everything
5. All the computations are performed with only one branch
Note : You can switch between dynamic chache and precomputed chache without branching
Here is my implementation with 0.002 timing
http://programming-challenges-solutions.blogspot.in/2012/09/uva-100-programming-challenges-skiena.html
Hi guys,
My code runs perfect on eclipse But on UVa shows
ERROR The 3n + 1 problem has failed with verdict Runtime error.
This means that the execution of your program didn’t finish properly. Remember to always terminate your code with the exit code 0.
I am trying hard to find error. Can you please tell me what changes are required??
—–My Code
import java.util.Scanner;
class Problem100 {
static int cycle_no;
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int p = 0, q = 0, min = 0, max = 0, result =0, max_cycle_no = 0;
p = scn.nextInt();
q = scn.nextInt();
if(p < q)
{
min = p;
max = q;
}
else{
min = q;
max = p;
}
for(int i = min; i <= max ; i++)
{
cycle_no = 0;
result = solver(i);// Function To find cycle no
if(max_cycle_no < result)
max_cycle_no = result;
}
System.out.println(p + " " + q + " " + max_cycle_no);
System.exit(0);
}
// Function To find cycle no
private static int solver(int p) {
cycle_no ++;
if (p == 1)
return cycle_no;
else if(p%2 == 1)
return solver(3*p + 1);
else return solver(p/2);
}
}
Hi all,
First of all thank you tantelore for sharing this. I don’t know if this is still active or not. But, I learned something from this and thought of sharing what I see.
If you look at first 20 sequences (n=1 to 20) you can see “even n” has short sequences unless its the upper limit. If its a “power of 2” its even shorter. This got me upto 0.018 secs.
hey i tried the same solution but it is showing WRONG answer while i m submitting online…any idea why??