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.