getting tle polo the penguin and test

help
, , ,
1

problem link: www.codechef.com/problems/PPTEST

my code: http://www.codechef.com/viewsolution/3500235

PLEASE HELP OPTIMIZE MY CODE

THANKS IN ADVANCE!!

2

Hi ansh!!
your solution is simply recursively computing the solution to the problem with n=100, it has a complexity of O(2^n) ie O(2^100) which will simply timeout. Also while recursing you are computing results of same problems again and again…why not simply store the results of the previously computed problems somewhere so that you donot need to recurse for that particular problem? In order to do this bulid a table for previously computed solutions and use it to find the answers to next problems…this approach is a dynamic programming approach with a complexity of O(n*w)…which will pass the given time limit…Hope this Helps :slight_smile:

1 Like