IdeaMonk

thoughts, ideas, code and other things...

Sunday, August 03, 2008

Hints for SPOJ COINS

Trying out COINS(Bytelandian Gold Coins) at spoj.pl ? not getting it? Try giving life to these cryptic ideas from my scratchpad -
while they speak of recursion, to speed up try memoization technique from dynamic programming.

Labels: , ,

4 Comments:

At August 3, 2008 at 7:51 PM , Anonymous Anonymous said...

what exactly do you mean by memorization in here?

 
At August 20, 2008 at 4:24 AM , Blogger Abhishek Mishra said...

see when you've got recursive solutions, on higher inputs the trace usually breaks to function calls on lower inputs and this becomes very repetitive for higher inputs. So, if you precalculate and store return values of the function for large number of small inputs, the faster your program works for those high inputs. as seen in this case. have a look at the analysis - Optimization by memorization

 
At October 7, 2008 at 1:16 PM , Anonymous Anonymous said...

you ment memoization? http://en.wikipedia.org/wiki/Memoization

 
At October 7, 2008 at 9:36 PM , Blogger Abhishek Mishra said...

Woops!!! thanks for correcting me.. its memoization actually and not memorization

 

Post a Comment

Subscribe to Post Comments [Atom]

<< Home