Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

The problem can be viewed here, since it's styled. I don't think I should just copy and paste.

And here's my code. I implemented recessive function and dynamic programming to solve it.

It can successfully passed UVa Judge with a score of 612ms, but it's not fast enough for this site. Which test my code against 200000 lines of input, and giving only 2s.

#include <cstdio>
#include <iostream>

int cycleLength(long long int);

int cycleLengthResult[1000001];

int main(int argc, char *argv[])
{
    int i = 0, j = 0, cur = 0, max = 0, k = 0, s = 0;
    for (i = 1 ; i < 1000001 ; ++ i ) cycleLength(i);

    while ( scanf("%d%d", &i, &j) != EOF )
    {
        printf("%d %d ", i, j);
        if ( i > j )
        {
            s = i;
            i = j;
            j = s;
        }
        max = 0;
        for ( k = i ; k <= j ; ++ k )
        {
            cur = cycleLengthResult[k];
            if (cur > max) max = cur;
        }
        printf("%d\n", max);
    }

    return 0;
}

int cycleLength(long long int arg)
{
    if ( arg > 1000000 )
    {
        if (!(arg & 1))
            return 1 + cycleLength(arg/2);
        else
            return 1 + cycleLength(arg*3+1);
    }
    if (!cycleLengthResult[arg])
    {
        int valueForArg = 0;
        if (arg == 1)
            valueForArg = 1;
        else if (!(arg & 1))
            valueForArg = 1 + cycleLength(arg/2);
        else
            valueForArg = 1 + cycleLength(arg*3+1);

        cycleLengthResult[arg] = valueForArg;
    }
    return cycleLengthResult[arg];
}
share|improve this question
2  
Why are you using the C standard library and C programming idioms in what is apparently supposed to be a C++ program? –  Paul R Dec 30 '12 at 18:11
    
@Paul R I was told that scanf and printf will be faster than com and cout. And on the compiler provided by zerojudge.tw, you will need cstdlib. –  Shane Hsu Dec 30 '12 at 22:20
    
This is also known as the Collatz Conjecture, and there's also the XKCD view on it too. –  Jonathan Leffler Jan 1 '13 at 7:52

2 Answers 2

up vote 4 down vote accepted

I took an elective last semester in which we had to do UVa questions. Just dug up my old UVa 100 submission, and I have a few suggestions for speed (mine was accepted in 200 ms, though I suspect it could be optimized a ton more).

The main thing I see is that you shouldn't use recursion. Due to the setup cost of calling functions, iteration is going to be way faster (in some situations the same stack frame can be reused, but I doubt that optimization is being done in your code).


Though that is my main suggestion, there are a few very minor algorithmic optimizations that can be noted mathematically.

t(n) = 1      if n is 1
     = 3n + 1 if n is odd
     = n / 2  if n is even

c(n) = number of times t(n) will happen
(terrible math syntax here, but erm... go with it)

Now, the approach I took was to build a table bottom up. Basically an array like int m[1000001].

Then a loop like:

for (int i = 1; i <= 1000000; ++i) {
    if (i % 2 == 0) {
        //We know that i / 2 must already be set, so we can just do a constant time look up
        //(your code already does this implicitly through the recursion)
        m[i] = 1 + m[i / 2];
    } else {
        m[i] = cycleLength(i);
    }
}

Nothing special about this loop; it's just the iterative form of your code.

There is an odd little optimization you can make though:

if (i % 2 == 0) {
    m[i] = 1 + m[i/2];
} else if (i % 8 == 5) {
    m[i] = 4 + m[3 * ((i - 5) / 8) + 2];
} else {
    m[i] = cycleLength(i);
}

The theory here is that for any j < i, you know that m[j] is populated. Thus, if you can do some manipulation to get m[i] = c + m[f(i)] such that f(i) < i you can do a constant time look up rather than the potentially enormously expensive cycleLength call.

It's the same concept in the 1 + m[i / 2] situation, just weirder.

If i mod 8 = 5, then by definition, i = 8j + 5 for some integer j.

i = 8j + 5 = 2k + 1 with k = 4j + 2 thus i is odd.

So we follow the pattern:

8j + 5 -> 24j + 16 -> 12j + 8 -> 6j + 4 -> 3j + 2

Note the crucial part here: 3j + 2 < 8j + 5. This means that we can define m[i] in terms of 4 + m[3 * ((i - 5) / 8) + 2].

I'm too lazy to get out a pad of paper, but I suspect that more arithmetic trickery like this is possible (the weird situation of i mod 8 = 5 is something that the professor pointed out). Even without it, an iterative approach is easily fast enough to be accepted by UVa's online judge, but it does make a surprising 48 ms difference with my program.

share|improve this answer
    
@Corbin I read your answer, and will try it next week. –  Shane Hsu Dec 30 '12 at 14:33
    
@WilliamMorris Whoops, yup. Double typed it. –  Corbin Dec 30 '12 at 18:22
    
Don't know why I didn't accept this more than a year ago. This did the trick then. –  Shane Hsu Jan 31 at 2:55

The only places I have found that improve cycleLength (by 5-10%) are

  • reversing the (somewhat illogical) if (!(arg & 1)) conditions (not really sure if this had an effect though, as there seems no reason for it to)
  • and removing the test for arg == 1 by initialising cycleLengthResult[1] to 1:

    int cycleLengthResult[1000001] = {0, 1, 0}

It is also possible to extract the duplicated code to make the function more readable, although this does not improve the performance:

int cycleLength(long arg);

static inline int nextLength(long arg)
{
    long n;
    if (arg & 1) {
        n = (arg * 3) + 1;
    } else {
        n = arg / 2;
    }
    return 1 + cycleLength(n);
}

int cycleLength(long arg)
{
    if (arg > 10000000) {
        return nextLength(arg);
    }
    if (cycleLengthResult[arg] != 0) {
        return cycleLengthResult[arg];
    }
    return cycleLengthResult[arg] = nextLength(arg);
}

There might be ways to improve main but I didn't look at that.

share|improve this answer
    
I've read your answer, and will try it this week. –  Shane Hsu Dec 30 '12 at 14:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.