I used the same approach as said by editorialist with using segment tree for finding max element.
Is my solution O(n*log(n)) in worst case ?
Idk if its is but it seems to be O(n*log(n)).
##HERE is my solution.
1 Like
@pshishod2645 do you really think, @admin is gonna… shout at it? If in the last cook off… there were such nice test cases and no one spoke… out… so its better we make a habit of having weak test cases specially at CookOffs XDD…
@pshishod2645 The best solution will be at most logN, not saying ‘greedy’ will be the best. For finding the best just recurse up to depth of logN
@pshishod2645 The greedy solution will remove at least half the remaining profile each step. That’s going to give at most \log_2 n reservoirs. So, “actually” my statement was true. That doesn’t mean (and I did not say) that the greedy solution is the best, but it does give an upper limit on the number of reservoirs required in the best solution - because by definition of “best” it won’t have more reservoirs than the greedy solution.
In this, we are dividing the range into 2 unequal parts, with the best case being both of roughly equal size, giving O(log^2 N) complexity vs the worst case having O(N*logN) time complexity. one logN is due to calls to segment tree, rest due to recursive calls.
Well, I have never faced such scenario since I never initialized array size this way as you did in first.
I do not know.
Glad you liked 
That’s the “greedy” algorithm; it will fail to find the best solution sometimes, for example
1 3 2 9 8 6 7 4 5
where the greedy approach will take 3 reservoirs but 2 is best case.
1 Like
The optimal solution is Right oriented reservoir at the first and third position.
Can anyone please tell me in which case we will get the answer more than 2?
Can anyone please tell me in which case we will get the answer more than 2?
Hello.
Why is this problem not open for practice anymore?
It’s divide and conquer which is O(Nlog(N)) and your condition makes it even more faster.
int sol(int start,int end){
int ind=start;
for(int i=start;i<=end;i++){
if(arr[i]>arr[ind]){
ind=i;
}
}
if(ind==start or ind==end)
return 1;
//cout<<ind<<' '<<endl;
return 1+ min(sol(start,ind-1),sol(ind+1,end));
}
this code get’s ac but
int sol(int start,int end){
if(start>end)
return 0;
int ind=start;
for(int i=start;i<=end;i++){
if(arr[i]>arr[ind]){
ind=i;
}
}
//cout<<ind<<' '<<endl;
return 1+ min(sol(start,ind-1),sol(ind+1,end));
}
gets tle
7
2 7 4 8 5 6 1