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.
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
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))
sorry karan gave similar test case
XD
\hspace{0mm}
I like such problems where the obvious greedy/innocent solutions fail
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…)?
\hspace{0mm} \hspace{0mm}
Sure I will give you test cases till you get AC. No issues.
4
0 1 2 3
check this
You can find test cases on your as well.
Bug Finder - A GUI application to compare source codes.
Check this. Take any AC code. Take you code. make a random test case generator( very simple n=rand()%10, then output 10 random values etc.) or give test cases randomly and check which test case fails.
no issues \hspace{0mm}