Tuesday, September 10, 2013

How I solved UVa 100 - 3n + 1

Problem link: 3n + 1
Many thanks to Praveen and Prasad for bringing this problem back to me after many years. I had solved this problem long back and it had taken more than 3s initially (with AC of course!). 
Prasad started to solve it again and I jumped in too. This time, I submitted 2 solutions:
1. Pre-compute the cycle length of all numbers [1,999999]. Read the inputs and print the outputs from the pre-computed array. Time = 0.442s.
2. I had suggested to Prasad to try and use the idea of computing the cycle length of a number just once. In the previous solution, we compute the cycle length of a number multiple times. I used a stack to keep track of the numbers and once I see a pre-computed cycle length for any number in the sequence, I just unwind the stack and set the cycle lengths for all numbers on the stack. Time = 0.062s.
Both the solutions use scanf, printf, & (bitwise and), >> (right shift), *=, +=.
Looks like the OJ (online judge) runs on really fast processors these days! The OJ upgrade is on :-)
One more spoiler: here's the source code :-) Am finally onto GitHub and it is befitting to add the source of the very first problem I solved years back and solved again due to Prasad.

2 comments:

  1. :-) You and Alluri-gaaru brought this problem back again and so did Sai-gaaru. It is filled with fun to keep discussing the UVa problems. It is a pleasure to be associated with you guys.
    -raghav

    ReplyDelete