PUMPWAT - EDITORIAL

general
, , , , ,
21

I used a queue based solution with O(n2) worst time complexity and it passed in 0.03s.

Link

22

https://www.codechef.com/viewsolution/21138623
could you tell me what is wrong with my solution i just found the max then after removing the smaller side of th hills i found the nex max and so on getting wrong answer.

23

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.

24

Well, I have never faced such scenario since I never initialized array size this way as you did in first.

I do not know.

25

Glad you liked :slight_smile:

26

I used divide and conquer, worst case complexity O(nlogn).
here is my solution.

27

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.

28

for sequence 4 1 9 5 7 3 2

is there consecutive i and i+1 such that both facing opposite direction for optimal solution

29

The optimal solution is Right oriented reservoir at the first and third position.