100 - The 3n + 1 problem

[imkat]

I tried many inputs and the outputs were all correct.However,I still get a WA.here is my code:

Code: Select all

const maxn=1000000;
var
   i,a,b,max:longint;
   l:array[0..maxn] of longint;
function tryl(n:int64;t:longword):longint;
var
    nextn:int64;len:longint;tmp:extended;
begin
    if n<=maxn then begin
        if l[n]>0 then tryl:=l[n]+t else begin
            if n mod 2=0 then tmp:=n div 2 else tmp:=n*3+1;
            nextn:=round(tmp);
            len:=tryl(nextn,t+1);
            tryl:=len;
            if n<=maxn then l[n]:=len-t;
        end;
    end else begin
        if n mod 2=0 then tmp:=n div 2 else tmp:=n*3+1;
        nextn:=round(tmp);
        len:=tryl(nextn,t+1);
        tryl:=len;
        if n<=maxn then l[n]:=len-t;
    end;
end;
begin
    l[1]:=1;
    for i:=2 to maxn do begin
        l[i]:=tryl(i,0);
    end;
    while true do begin
        if eof() then break;
        readln(a,b);
        max:=0;
        if a<=b then begin
            for i:=a to b do begin
                if l[i]>max then max:=l[i];
            end;
        end else begin
            for i:=b to a do begin
                if l[i]>max then max:=l[i];
            end;
        end;
        writeln(a,' ',b,' ',max);
    end;
end.

Why is it WA?

who can help me?

[raza]

My code for this problem was accepted but the best i have been able to attain so far is a run time of 4.086 seconds and 388 Kb of virtual memory.
I have seen the ranklists and am surprised to see that this problem has been solved with minimum memory and 0 CPU time.
Now,i am trying to optimize my code , by trying to use the technique of memorization suggested in this thread.I am using a linked list to store numbers and their cycle lengths and this list is used so that i dont calculate the cycle lengths twice for any number.
But im getting time limit exceeded. Below is my C code.

Code: Select all

#include <stdio.h>

typedef struct node
{

     int data[2] ; /* Number and its cycle length */

     struct node * ptr ;   

} node ; 

node * p ;

int main()
{
    
     int i , j  ; 

     int cycle_length , max_cycle_length = 0 ;

     int calculate_cycle_length(int num);

     while(scanf("%d %d",&i,&j) == 2)
     {
              
              /* Remember original i and j incase they are out of order */

             printf("%d %d ",i,j);

              /* If i and j out of order swap */

              if(i > j)       
              {
                   i = i+j ;

                   j = i - j ;

                   i = i - j ;
              }

              while(i <= j)
              {
                       cycle_length = calculate_cycle_length(i) ;

                       if(cycle_length > max_cycle_length)
                                       max_cycle_length = cycle_length ;

                       i++ ;                              

              }

              printf("%d\n",max_cycle_length);

              max_cycle_length = 0 ;

     }


}

int calculate_cycle_length(int num)
{

    int cycle_length = 0 , q = num ;

    void append(int num,int cycle_length);

    node * searchi(int i);

    node * temp ;

    /* Check if num is already present in the list or not */

    if((temp = searchi(num)) !=  NULL) /* Present */
    {
          /* return cycle length of num */

          return temp->data[1] ;
    }
    else
    {

        while(num != 1)
        {
    
            if(num%2 == 0)
                 num/=2 ;
            else
                 num = (num*3)+1 ;
    
            cycle_length++ ;    

            if((temp = searchi(num)) !=  NULL) /* If num already exits in the list  */
            {

                  
                  /* cycle_length = cycle_length + cycle length of num */

                  cycle_length+=temp->data[1] ;

                  /* Add this data to list */

                  append(q,cycle_length);

                  /* return cycle_length */
                  
                  return cycle_length ;

            }
     
        }  
    
        cycle_length++ ;  /* Count the 1 at the end too */

        /* Add this data to list */

        append(q,cycle_length);

        /* return cycle_length */
    
        return cycle_length ;    
     }   
    
}

node * searchi(int i)
{

     node * temp  = p ;

     if(temp == NULL)
          return NULL ;
     else
     {     
         while(temp->ptr  != NULL)
         {
                  if(temp->data[0] == i)     
                                return temp ;
                  else
                      temp = temp->ptr ;    

                      
         }
            
         if(temp->data[0] == i)         
                   return temp ;
         else                 
                   return NULL ;
     }    
}


              

void append(int num,int cycle_length)
{
        struct node * temp , *r ;

        if(p == NULL) /* If the list is empty create first node */
        {
              temp = malloc(sizeof(node));

              temp->data[0] = num ;

              temp->data[1] = cycle_length ;
              
              temp->ptr = NULL ;

              p = temp ;
        }
        else
        {
            temp = p ;

            /* go to the last node */

            while(temp->ptr != NULL)
                    temp = temp->ptr ;

            /* add node at the end */

            r = malloc(sizeof(node));

            r->data[0] = num ;

            r->data[1] = cycle_length ;
            
            r->ptr = NULL ;

            temp->ptr = r ;                

        }

               

} 

Plese help me optimize my code and fix the time limit exceeded error.

Thanks a lot

[raza]

Hi ,

This is something which should be posted in the problemset forums and i have did that but since i havent received any reply yet there for a long time ,i thought ill post it here again and hope to get a response.
Actually despite having solved the problem ,im still interested because i want to improve my algorithm development and problem solving skills and i think the only way to do that is to not stop after having solved a problem but think how the solution could be made better,isnt that correct ?
Im new to this site and my question is about the 3n+1 problem in volume 1. I coded my solution in C and my solution has been accepted by the judge with a CPU time of 4.086 seconds and memory usage of 388 Kb.Ive seen the ranklists and i see that people have implemented the solution in C with 0 CPU time and minimum memory usage.
I then solved the problem again , this time using memorization , and i hope ive applied memorization correctly. I used a linked list for saving numbers and their cycle lengths so that no number is calculated twice. But this time round im getting a time limit exceeded message from the judge.

My C code where ive implemented memorization using a linked list is below :

Code: Select all

#include <stdio.h>

typedef struct node
{

     int data[2] ; /* Number and its cycle length */

     struct node * ptr ;   

} node ;

node * p ;

int main()
{
   
     int i , j  ;

     int cycle_length , max_cycle_length = 0 ;

     int calculate_cycle_length(int num);

     while(scanf("%d %d",&i,&j) == 2)
     {
             
              /* Print original i and j */

             printf("%d %d ",i,j);

              /* If i and j out of order swap */

              if(i > j)       
              {
                   i = i+j ;

                   j = i - j ;

                   i = i - j ;
              }

              while(i <= j)
              {
                       cycle_length = calculate_cycle_length(i) ;

                       if(cycle_length > max_cycle_length)
                                       max_cycle_length = cycle_length ;

                       i++ ;                             

              }

              printf("%d\n",max_cycle_length);

              max_cycle_length = 0 ;

     }


}

int calculate_cycle_length(int num)
{

    int cycle_length = 0 , q = num ;

    void append(int num,int cycle_length);

    node * searchi(int i);

    node * temp ;

    /* Check if num is already present in the list or not */

    if((temp = searchi(num)) !=  NULL) /* Present */
                  return temp->data[1] ; /* return cycle length of num */
    else
    {

        while(num != 1)
        {
   
            if(num%2 == 0)
                 num/=2 ;
            else
                 num = (num*3)+1 ;
   
            cycle_length++ ;   

            if((temp = searchi(num)) !=  NULL) /* If num already exits in the list  */
            {

                 
                  /* cycle_length = cycle_length + cycle length of num */

                  cycle_length+=temp->data[1] ;

                  /* Add this data to list */

                  append(q,cycle_length);

                  /* return cycle_length */
                 
                  return cycle_length ;

            }
     
        } 
   
        cycle_length++ ;  /* Count the 1 at the end too */

        /* Add this data to list */

        append(q,cycle_length);

        /* return cycle_length */
   
        return cycle_length ;   
     }   
   
}

node * searchi(int i)
{

     node * temp  = p ;

     if(temp == NULL)
          return NULL ;
     else
     {     
         while(temp->ptr  != NULL)
         {
                  if(temp->data[0] == i)     
                                return temp ;
                  else
                      temp = temp->ptr ;   

                     
         }
           
         if(temp->data[0] == i)         
                   return temp ;
         else                 
                   return NULL ;
     }   
}


             

void append(int num,int cycle_length)
{
        struct node * temp , *r ;

        if(p == NULL) /* If the list is empty create first node */
        {
              temp = malloc(sizeof(node));

              temp->data[0] = num ;

              temp->data[1] = cycle_length ;
             
              temp->ptr = NULL ;

              p = temp ;
        }
        else
        {
            temp = p ;

            /* go to the last node */

            while(temp->ptr != NULL)
                    temp = temp->ptr ;

            /* add node at the end */

            r = malloc(sizeof(node));

            r->data[0] = num ;

            r->data[1] = cycle_length ;
           
            r->ptr = NULL ;

            temp->ptr = r ;               

        }

               

}

Why am i getting a time limit exceeded message and also please suggest some ways if any how i can improve the performance of my code.

Thanks a lot

[little joey]

I really don't think you should be discussing specific problems in the algorithms section. But I agree that problem is so much "over-discussed" that the chances of getting a decent reply there are minimal.

About memoization (there's no r in that word): the idea is to never calculate the same answer twice, but look it up when requested the second, third, etc. time. For this problem, we could have an array "int precalc[]" to store the cycle lengths for the values we already calculated. The problem is, that we don't know in advance how big the argument of the function will get, and chances are that it will be in the tens, if not hundreds of millions, which is too big a dimension for an array of integers. So we could make a compromise: for arguments up to some value we store their answers in an array, and for bigger values we calculate the answer the conventional way. In code:

Code: Select all

#define MAXVAL 1000000

int precalc[MAXVAL]; /* automatically initialized with zeros! which means: not calculated yet */

int cycle_length(int n){

   if(n==1) return 1;

   if(n>=MAXVAL){ /* too big to store, use conventional method */
      if(n%2==0) return 1+cycle_length(n/2);
      else return 1+cycle_length(3*n+1);
      }
   else if(precalc[n]>0){ /* already calculated, return it */
      return precalc[n];
      }
   else{ /* not yet calculated: calculate and store */
      if(n%2==0) return precalc[n]=1+cycle_length(n/2);
      else return precalc[n]=1+cycle_length(3*n+1);
      }
   }

I chose 1 million for MAXVAL, which seems reasonable: the bulk of the calls to cycle_length() will be for values below 1 million. (Note: I'm typing the code from the top of my head, without a compiler at hand, so there may be minor bugs.)

I hope that this gives you an idea what memoization/precalculation is about and how it is implemented in general. It's a very useful tool for a broad range of problems and quite easy to master. I think if you implement it this way, your runtime should get below 1 second. And for the very fast times: don't bother about them. Solve some more problems first and then come back later and think about possible improvements of your code.

Hope it helps (and is somewhat on topic by explaining a general algorithmic method).

[raza]

Hi little_joey,

Thanks a lot for explaing the memoization (i dont have a 'r' in there this time..hehe ) algorithm . This is a really useful and simple algorithm , and i now realise where i was going wrong earlier.
Your recursive algorithm led to CPU time of 0.110 and memory usage of 4304 .
I then implemented the same algorithm iteratively and was able to attain CPU time of 0.090 and minimum memory !. I had read in some textbooks that iterative algorithms are more efficient than their recursive counterparts and this seems to validate that point
Anyways, all thanks to you for taking the time out to explain this to me, despite this problem already been overdiscussed.
And yes, i will definitely follow ur advice, and solve more problems before thinking over optimization issues.

Thanks again

[piva]

[EDIT] Problem solved. I had to include <cstdio> to use printf() function

Hi, I'm new to the forums, and to C++ in the online judge, and I'm getting a Compile Error in problem #100 although I'm able to compile in my machine, running g++ version 4.1.2. I've searched the forums and sorry if it's been asked before but is my compiler out of date? Or should I use another compiler for C++ ? Special compiler options or prohibited libraries? My code is as follows:

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;

#define LEN(A) ((A).length())
#define SZ(A) ((A).size())
#define FOR(A, B) for(int A = 0; A < (int)B; A++)
#define IFOR(A, S, B) for(int A = (int)S; A < (int)B; A++)

int main()
{

int i, j;
while(cin >> i && cin >> j)
{
int max = 0;
IFOR(k, i, j + 1){
int n = k;
int atual = 1;
while(n != 1){
if(n % 2 == 1) n = 3*n + 1;
else n = n/2;
atual++;
}
if(atual > max) max = atual;
}
printf("%d %d %d\n", i, j, max);
}
printf("\n");
return 0;
}

Thanks in advance

[Tristan]

raza,
It's been almost a month since your post, so you've probably already solved your problem, or have lost interest, but I'll give my 0.02 anyway, for anybody else trying to speed up their code.

The goal of never calculating a cycle length twice is unreasonable, since the program potentially encounters A LOT of numbers. Every time you add a number to your linked list, your search gets more expensive and uses more memory. I think a better idea is to concede that some cycle lengths will be calculated twice and only memoize some fixed number of cycle lengths (1,000,000 seems to work well). Smaller numbers will be encountered much more frequently than large numbers, so memoize the smallest 1,000,000 numbers as you encounter them. With a fixed number of memoizations, you can store them in a simple array indexed trivially, getting rid of the need for an expensive and complicated search.

Further, the division by 2 can be bypassed. If you work through the 3n+1 problem by hand in base 2, it's obvious that the division by 2 just gets rid of trailing zeros. So, if n is of the form 2^p * q (i.e. it has p trailing zeros), you can just bit shift to the right p times: n >>= p;

There are many ways to count the trailing zeros, but the fastest one I've found so far is:

const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((n & -n) * 0x077CB531UL) >> 27];

The (n & -n) extracts the least significant 1 in n, and the rest does some neat trickery with a De Bruijn number. r gives the number of trailing zeros in n.

So, after p steps, 2^p*q looks like q.


Next, if n looks like 2^p*q + 2^p - 1 (i.e. n has p trailing 1s), then after 2p steps, n will look like 3^p*(q+1) - 1. You can count the trailing 1s the same way as before, just do n++ before doing (n & -n), so the trailing 1s turn into trailing zeros.
Then bitshift p times, multiply by 3^p, and subtract 1.

I was unable to make the trailing 1s trick efficient enough to be worthwhile, but maybe you can figure out a way.

Another possible optimization on the memoization is the observation that if n = 0,1,2,3,or 5 (mod 6), there is only one possible number which can precede n in the cycle: 2n. So we don't really need to save the cycle length of n if we save the cycle length of 2n. If a cycle reaches 2n, we don't need to go down to n, and since 2n is the only way to get to n, n is useless unless we want its cycle length. With this optimization, we only have to follow a cycle until we reach a number which is 4 mod 6 (assuming we've already saved its cycle length). You can even index your memory array so you don't have to do 3n+1 before looking up.

There are a lot of little optimizations to be had, once your program gets fast enough for them to matter. They can mostly be figured out by thinking about what your program is doing in base 2. Pen and paper are helpful.

In general, scanf and printf are faster than cin and cout.

If you are using a loop to do something, try to think of a way to do it without a loop (my cycle length function has no loops, although it does have recursion... I also try not to do more recursion than I need to).

There are some ideas.

[cpp_stu2]

:P You can see this web page
It may helps! :D
http://acm.uva.es/p/v1/100_fix.html

[kauedg]

I know its a easy problem but i cant get less than 10 secons of run time. Could somebody help me please?

Code: Select all

#include <stdio.h>

int Cycles(long n)
{
   long cycles;

   cycles = 1;

   if(n <= 0) return 0;

   while(n!=1)
   {
      if(n%2 != 0)
         n = (3*n)+1;
      else
         n /= 2;

      cycles++;
   }

   return cycles;
}

int main()
{
   unsigned int i, j, n, clmax;
   long c;

   while(scanf("%d",&i))
   {
      scanf("%d",&j);

      printf("%d %d ",i,j);

      if(i>j)
      {
         n = i;
         i = j;
         j = n;
      }

      clmax = 0;

      for(n=i; n<=j; n++)
      {
         c = Cycles(n);
         if(c > clmax) clmax = c;
      }

      printf("%d\n",clmax);

   }
   return 0;
}

this is the answer I received:
Your program has used more time (10.018 seconds) than the maximum allowed for this problem by this judge (10 seconds).[/quote][/code]

[Jan]

Search the board first. Don't open a new thread if there is one already.

[kauedg]

I know its a easy problem but i cant get less than 10 secons of run time. Could somebody help me please?

Code: Select all

#include <stdio.h>

int Cycles(long n)
{
   long cycles;

   cycles = 1;

   if(n <= 0) return 0;

   while(n!=1)
   {
      if(n%2 != 0)
         n = (3*n)+1;
      else
         n /= 2;

      cycles++;
   }

   return cycles;
}

int main()
{
   unsigned int i, j, n, clmax;
   long c;

   while(scanf("%d",&i))
   {
      scanf("%d",&j);

      printf("%d %d ",i,j);

      if(i>j)
      {
         n = i;
         i = j;
         j = n;
      }

      clmax = 0;

      for(n=i; n<=j; n++)
      {
         c = Cycles(n);
         if(c > clmax) clmax = c;
      }

      printf("%d\n",clmax);

   }
   return 0;
} 

this is the answer I received:
Your program has used more time (10.018 seconds) than the maximum allowed for this problem by this judge (10 seconds).

[helloneo]

Your program doesn't end..
scanf() returns EOF instead of 0 at the end..

[kauedg]

made

Code: Select all

while(scanf("%d",&i) == 1 )

and worked! thanks! =D

Your C program has solved Ok the problem 100 (The 3n + 1 problem) in 4.172 seconds using as much as 392 kbytes of virtual memory.
Congratulations!

[sylar]

Plz help.
I am facing the same problem.
My code for problem set 10146 is running properly on my machine. Tried with gcc as well as Dev-cpp compilers. But it is giving compiling error on submitting.
I am new and joined today only.
My code has some simple operations of vector and string only.
I have included iostream, vector ,string (also tried cstring) . Plz help as i am struck.
Thanks in advance.

[Jan]

It would be better if you post your code.