26th October, 2010, my last day of stay in Siliguri(My home town) in the durga puja vacations. This was the second consecutive instance when there was a SRM on the same evening when I was to board a train. Fortunately both time my train was late (courtsey to Indian railways :P) and I was able to compete.
After my good performance in the last SRM I was again back to div-1. The first problem was of 300 points so it was harder than normal level 1 problem. It took me 30 mins to code I tried my best to think of all the cases.
The Question is as follows :-
Given two integer values start and terminate, you are required to perform certain operations on the start value. The operations were simple "*, +, /, -". You need to take the start value as the two operands and also store the result in the start value. If start=5, and you perform a "*" operation, then start=start*start, start becomes 25. You need to perform minimum number of operations to reach the terminating value, and concatenate the operators. If the minimum number of operations is same then return the lexicographically first string.
I thought and first thing that came in my mind was BFS. I coded a nice BFS solution, and then I thought that using the divide operation we can make the start value 1 and then we could reach the terminating value. So i applied BFS twice with the given start value and start value as 1. Everything seemed fine. I hoped it to pass the system test.
I had missed one critical thing, I was returning the answer if there was any with the given start value, but the answer with start value as 1 and "/" operation added to the beginning could be the answer with less number of operations. This cost me a couple of rating points, and my hope of entering top 100 in India :( :(. Its always better luck next time. I am still in div-1 :)
No comments:
Post a Comment