Gold is a hot commodity in today's world but is even hotter in Byteland. In Byteland the monetary policy is very peculiar. This is the situation faced there : http://www.codechef.com/problems/COINS/
Okay, normally, the person approaching the problem figures if the sum of n/2 , n/3 and n/4 is greater than n, then voila! sorry, that's too easy. Consider n/2 to be a.The fact that when considering a as a/2, a/3 and a/4, the sum could be greater than a has been missed. The same is the case with n/3 and n/4 and its n/2, n/3 and n/4 and so on.....But how does one solve such a problem?
The solution dawned upon me after a long time. There is no linear data structure, that can hold an arbitrary number of values and be useful for this program.A tree is one possible solution.But again, the complexity of traversing and then removing nodes and replacing them by larger values is too high. The simplest solution is to use a recursive function that does the job for you. No large data structures are needed because the recursive functions stack will suffice. So after going on to code with this technique, i discovered that i got the solution.But, the CodeChef judges are very difficult to please, they were not just looking for the solution, but wanted the answer to be found within 5s and 64MB of memory.This is when i fell in love with coding more than ever. After a lot of thinking i somehow realized that if i cache the data which has already been calculated, then it would save time of computing the same values each time. So , after caching and submitting and anxiously waiting for the result, i was indeed happy to see an accepted solution. if you want my code, e-mail me at quakerr90@gmail.com
Okay, normally, the person approaching the problem figures if the sum of n/2 , n/3 and n/4 is greater than n, then voila! sorry, that's too easy. Consider n/2 to be a.The fact that when considering a as a/2, a/3 and a/4, the sum could be greater than a has been missed. The same is the case with n/3 and n/4 and its n/2, n/3 and n/4 and so on.....But how does one solve such a problem?
The solution dawned upon me after a long time. There is no linear data structure, that can hold an arbitrary number of values and be useful for this program.A tree is one possible solution.But again, the complexity of traversing and then removing nodes and replacing them by larger values is too high. The simplest solution is to use a recursive function that does the job for you. No large data structures are needed because the recursive functions stack will suffice. So after going on to code with this technique, i discovered that i got the solution.But, the CodeChef judges are very difficult to please, they were not just looking for the solution, but wanted the answer to be found within 5s and 64MB of memory.This is when i fell in love with coding more than ever. After a lot of thinking i somehow realized that if i cache the data which has already been calculated, then it would save time of computing the same values each time. So , after caching and submitting and anxiously waiting for the result, i was indeed happy to see an accepted solution. if you want my code, e-mail me at quakerr90@gmail.com
