[problem statement][1]
[1]: https://www.codechef.com/COOK99A/problems/PUMPWAT
[solution code][1]
[1]: https://ideone.com/sAcWDf
approach:
Considering the heights in decreasing order, every uncovered mountain has two choices (left or right).
When a mountain is marked left/right, its index is inserted into the corresponding set.
The answers for these choices have been stored in dp[][].
you defined fn as fn(vii a, …)
When you call fn this causes a copy to be made of a, which is O(n)
later in fn we call fn multiple times in a loop. In the worst case we will loop over all elements, and call fn for each one, hence O(n^2)
this doesn’t fit in time bounds -> TLE
a solution against the $O(n) copying is to pass variables by reference:
fn(vii& a,);
in this way you don’t copy but read/write the original. As you are only reading this should cause no problems.
you may have to do the same with the sets, but then you must undo your changes before returning.
I’m not sure if after these fixes you won’t get TLE as my approach was different. It should certainly help.
I’ve updated the code like you said but still getting TLE :(.
Please note: 0 means left and 1 means right choice
The complexity of my code is O(n), as fn() can only be called at max n times, in case when the input array is sorted in decreasing order and every mountain is chosen for left recursively till the smallest, then dp[n-1][0] will store 1. Then my algo will backtrack for right from the smallest mountain and dp[n-1][1] will also store 1, returning min(dp[n-1][0], dp[n-1][1]) to previous state i.e. fn(n-2, 0), thus dp[n-2][0] = 1 + min(dp[n-1][0], dp[n-1][1]), then fn(n-2, 1)…
You still have a worst case O(n) loop within fn(…). An example of the worst case:
1
100000
1 2 3 4 … 99998 99999 100000
this will be O(n^2) I am not sure if a top-down approach exists, I solved it using bottom-up.