Could someone please point out why my code for the PUMPWAT problem receives WA? I have used the approach of finding the next greater element and previous greater element for each particular hill and then using two arrays left and right to store the minimum number of reservoirs pointed in the left and right direction before and after each element respectively. I am also taking care of the corner cases but I am absolutely clueless as to why my code receives WA.
@anon55659401, @l_returns , anybody??
3 Likes
Will surely find you bug. But am very busy at the moment. Will debug after 16th if that’s ok with you?
Ping me here again if I don’t reply on 17th date of this month.
Okay 
…
First things first! Make sure to check out the code for next and previous greater element from Geeksforgeeks as their code is perfect.
Step-2:- You have to find an index ‘x’ which does your work in least number of reservoirs…Make sure you are counting the number of reservoirs needed in left and right properly…
Step:-3 Make special case for , when the largest element is at the end or beginning
This is the case where your solution will fail, greedy won’t work
:—>1 3 2 9 8 6 7 4 5
where the greedy approach will take 3 reservoirs but 2 is best case.
2 Likes
Hey optimal is not DP i think. Its greedy only. divide an conquer works.
This should work. I did that as well
Where did I say dp? The optimal solution is:- Check for every ‘x’ how many guys would be in left and right, by using next and previous greater element concept of stacks, over and out!!!
okay my bad.
\hspace{0mm}
1 Like
1
10
8 0 1 2 3 9 4 5 6 7
This should give 2 ( right side from 8 and right side from 9 as well. but you code gives 3.
Please try to debug or explain me you approach a bit in case you can’t solve still.
Mine is simple as well. do check its simple divide and conquer.
I will brief my solution.
Find max element from array. and ans = min( ans(rightside) , ans(leftside));
Use recursion here.
Now how to find max element to pass in given time limit ?
Just use simple Segtree with range max query. Or any other method which can find max from given subarray in O(log(n))
2 Likes
sorry karan gave similar test case 
1 Like
XD
\hspace{0mm}
I like such problems where the obvious greedy/innocent solutions fail
1 Like
Sorry for delay \hspace{0mm}
Thanks for your help @anon55659401 and @l_returns, I debugged my code accordingly and now it gives correct answer to both of your testcases, but still WA 
…Still could you guys give some other test case or please help me out debugging (I know it’s irritating, but still…)?
1 Like
\hspace{0mm} \hspace{0mm}