UVa problem 100: sample code, sample algorithm

UVa problem 100 (3n + 1) is a pretty straightforward problem. There is one tricky part though. That i is not necessarily always less than j. So one needs to watch out for the case when i is greater than or equal to j.

Also one, can speed things a little bit by using the bit-shift operator for division or multiplication. A division by 2 is similar to a right bit-shift by 1 bit. A multiplication by 2 is equivalent to a left bit-shift by 1 bit.

That is, x / 2 is equivalent to x >> 1; x * 2 is equivalent to x << 1.

001 #include "stdio.h"
002 
003 int main() {
004   char line[100];
005 
006   int   i
007       , j
008       , n
009       , n0
010       , m
011       , cycle
012       , max
013       ;
014 
015   while (fgets(line, 100, stdin)) {
016     sscanf(line, "%d %d", &i, &j);
017 
018     if (i <= j) {
019       for (n0 = i, max = 1; n0 <= j; n0++) {
020         n = n0;
021         for (cycle = 1; n != 1; cycle++) {
022           m = n & 1;
023           if (m) {
024             m = n << 1;
025             n = m + n + 1;
026           }
027           else {
028             n >>= 1;
029           } 
030         }
031         if (cycle > max) {
032           max = cycle;
033         }
034       }
035     }
036     else {
037       for (n0 = j, max = 1; n0 <= i; n0++) {
038         n = n0;
039         for (cycle = 1; n != 1; cycle++) {
040           m = n & 1;
041           if (m) {
042             m = n << 1;
043             n = m + n + 1;
044           }
045           else {
046             n >>= 1;
047           } 
048         }
049         if (cycle > max) {
050           max = cycle;
051         }
052       }
053     }
054 
055     printf("%d %d %d\n", i, j, max);
056   }
057 
058   return 0;
059 }

UVa problem 11173: sample algorithm

To solve UVa problem 11173 (Grey codes), one needs to know a trivia. I know it's quite unfair but that's the way it really is.

I actually spent hours trying to code this thing, trying to accurately simulate the reflection algorithm so vividly and exquisitely described by the problem. Then when I submitted, the online judge said I maxed out the time limit. Then I spent a few more hours figuring out how in the world to speed up this program.

Turned out the vivid description was a trick, a deception into leading me that that was the way to solve the problem. It was to divert my attention into thinking that there was no other way to solve it but to manually do the instruction on reflection step by step.

Then after surrendering, after some while, I thought that maybe there's some clue out there in Google. So I looked up "gray codes" in Google, and guess what? You guessed right. There was a trivia I had to know. To convert from binary to gray code, one only needed a bit shift and an xor bit-wise operation. Try googling it up.

The formula is disappointingly just a single statement to solve this problem:

g = b ^ (b >> 1);

where g stands for the gray code and b stands for the binary number.

That simple and it took me about 4 hours to figure this out. When I learned of this trivia, it took me less than 5 minutes to solve the problem. It's crazy.