PUMPWAT - EDITORIAL

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Alei Reyes
Tester: Aleksa Plavsic
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Previous and Next greater element, Observations.

PROBLEM:

Given heights H of N hills, we can place reservoirs on any number of hill, to provide water. Water flows from the reservoir in the chosen direction until reaching a hill with height strictly greater than the height of the hill with the reservoir. Find the minimum number of reservoir required to supply water to all N

OBSERVATION

  • If first or the last hill has the maximum height, We can just place a reservoir at that hill, oriented toward the other hill, covering all hills using 1 reservoir itself.
  • It can be proven that in the optimal placement of reservoir, there doesn’t exist two positions i, j given i < j containing reservoirs such that reservoir at position i is oriented rightwards while reservoir at position j is oriented toward left.
  • There exist two consecutive positions i and i+1 such that both have a reservoir, and both are oriented in opposite directions.

EXPLANATION

This problem is just observations, so we shall discuss them first. Handle the case were maximum element occur at either end separately.

Observation: In optimal placement of reservoir, there doesn’t exist two positions i, j given i < j containing reservoirs such that reservoir at position i is oriented rightwards while reservoir at position j is oriented toward left.

Proof: Let’s assume that in optimal placement and orientation of reservoirs, there exist two positions i and j such that i < j, there is reservoir at both positions, the reservoir at position i is oriented toward the right while reservoir at position j is oriented toward left.

The final arrangement will look something like this. …LR…LR… (Notice reservoirs in bold).

Since all heights are distinct, Either H[i] < H[j] or H[i] > H[j]. Also, No hill in range (i, j) have height Greater than max(H[i], H[j]) otherwise water flow cannot reach that hill. Now, If H[i] > H[j], The water flow from reservir shall cover all hills including hill j implying that the reservoir at position j is useless, and can be removed. Similar explanation follows if H[i] < H[j].

This contradicts our assumption that this arrangement was optimal.

Hence, All reservoirs from left up to a certain reservoir at position x are oriented towards left, while all reservoirs after position are oriented right.

Now, the Optimal arrangement looks like …L…L…R…R.

But, If water flow is to reach all hills, there should be no gap between Rightmost left-oriented reservoir and Leftmost right-oriented reservoir otherwise no water can flow toward the hills in the gap between those two reservoirs.

The last observation is, Suppose we have placed a left-oriented reservoir at position x. Then the reservoir immediately to the left which should have a reservoir should be the nearest hill with strictly higher height that hill at position x on the same side.

The reason is, suppose y is the nearest position, y < x such that H[y] > H[x], If we place at any position z < y, water can never reach position y since all resrvoir to left of position x are oriented left. If any position z > y is chosen, water will never reach hill y, since H[z] < H[x] < H[y] holds for all z satisfying y < z < x. So, we place the next reservoir at position y.

Now, we can repeat this procedure os placing reservoir at the nearest position to the left which has strictly higher height than current hill height, till water reach hill 1 too.

The similar procedure can be applied toward right-oriented reservoirs.

Now, we know how to solve the problem if we know the position x, the position of Rightmost Left-oriented reservoir. Fortunately, we can try all positions from start to end if we can count the minimum number of reservoirs required at left and right side of x required to supply water at all hills in O(1). We can do this by calculating in advance, L[i] representing Number of left-oriented reservoirs required to supply water in range [1, i] and R[i] representing minimum number of right-oriented reservoirs to supply water to hills in range [i, N].

This can be calculated by finding Next greater element as well as previous greater element, which can be done using a stack. It’s details you can find here.

Final answer is min(2+L[PGE[i]]+R[NGE[i+1]]) for all i, where PGE means Previous greater element to left of H[i] while NGE[i] means next greater element to right of H[i].

With this, we depart until you open another editorial of mine. :stuck_out_tongue:

Editorialist’s suggestion: There also exist a divide and conquer type solution, which editorialist initially used to solve the task. It picked hill of maximum height hill to place reservoir, try both orientations and print the minimum of both. It has O(N*logN) complexity, due to calls to Segment tree.

Time Complexity

Time complexity is O(N) since we just iterate over an array and use stack operations.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

1 Like
2

Is codechef really so bad at making strong test cases, lately every contest that codechef is organising is having really weak test cases, and again this problem where my O(n^2) solution passed the TL very easily in just 0.04s.

Highly disappointed.

2 Likes
3

I am not sure if its O(n^2). Could you explain it to me?

4

Your solution is of O(nlog(n)) not O(n^2) . Divide & Conquer

5

It is divide and conquer but it is not O(n \log n) since the split will not necessarily be at the center. The worst case is O(n^2) similar to quicksort.

1 Like
6

I used a little bit of dp with previous and next greater element thing. For every index i if I open it to left then water will flow up to index just after previous greater element. So ans at that index was updated by ans[i]=min(ans[i],ans[pge[i]]+1). And if I open it to right then water will flow up to index just before the next greater element, Now I’ll update ans at index (nge[i]-1) by ans[nge[i]-1]=min(ans[nge[i]-1],ans[i-1]+1). At last I printed ans[n]. click here to see my code.

7

@vipsharmavip, not everything that divide a segment in two parts is O(nlogn), it’s much similar to quick sort worst case, like splitting can be non-uniform, and I can even construct a case where this is really O(n^2)

8

Yes, but if u bound depth of recursion to logN, which you can prove is indeed maximal answer u get O(nlogn).

1 Like
9

@nidzulandz5 - Yes, a greedy solution (taking the bigger part of the remaining landscape each time from the remaining max hill) is less than \log n, so the best solution will be also.

10

@joffan, but that greedy solution gave wrong answer for me. And, that’s actually not true.

11

@nidzulandz, can you shed some light on the proof you are talking about, as I still think it is O(N^2) in the worst case, for example consider the case where elements at even indexes (1-indexing), are decreasing and greater than elements at odd-index.

For example : consider this.

1 5 1 4 1 3 1 2 1

12

int N = 1e9, n = 1e5;

for(int i=1;i<n;i+= 2)h[i] = N - i;

for(int i=0;i<n;i+=2)h[i] = 1;

My code takes 9.01s, on this input .

I don’t know why @admin is silent on this.

13

What is wrong with my solution, I am getting TLE, whereas many submission for this problem has similar code as mine and same logic.

www.codechef.com/viewsolution/21138970

14

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.

I am not sure because I m dividing it in two parts and then applying the recursive algo.

So it is like binary tree… So seems like not O(n*log(n)) in worst case due to recursive calling.

What do you guys think?

1 Like
15

@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…

16

(too long for a comment lol)

On case of weak TC, I see some people wanting an @admin response. Not an official response, but I think I know him/her and cookoff-preparations good enough to answer this.

Well, I will kind of defend the setter here. The test cases were not ridiculously weak - its just that the condition of “If maximum is at one of ends of subarray - terminate and return 1” hacked the large TC which was designated as worst case (I assume).

Like, the worst case is similar to worst case of quicksort - I think its very specific. I got 4 TLEs because I missed that good condition and wrote “If size==1, return 1” - so TCs were not weak, its just that this case was perhaps overseen/not expected. And if you consider that the official solution aint divide and conquer, you’d give setter benefit of doubt.

Preparation for cookoff is very hectic. At times there are multiple last moment changes made to adjust problems to a better difficulty. Even in this problem, initially duplicate heights were allowed which was changed later.

Talking about TCs in long now-

Regarding weak TC in long - lets face it, you have 10 days to break them. There are multiple heuristics to break random cases, especially if T=1 per file - this combined with 10 days time you can reverse engineer the test cases to get AC. In these instances, the definition of strong TC is redefined - “If making strong Test cases for a problem is very difficult, or its expected that contestants can use heuristics, make sure they waste a LOT of time there (especially in short contests).” With that in mind, with CPCOMP took you over 5 hours to solve, I guess TCs are ok. Of course, they could have been better, no denying that, I am simply saying that they were not trash.

And lastly, heuristics is also a skill. Like, getting a deterministic solution to every problem is difficult. If you can get a solution which uses randomness of TCs, and prune it to work on specific manual cases, or perhaps if you find various optimizations to make your code work under different conditions/inputs, I feel its good. It requires skills. A gray coder just starting cp cannot do heuristics - you need skills, you need concepts for that. Once you become good to a level, and are given 10 generous days for a problem perhaps you’d make your non deterministic solution pass with little difficulty.

Like, on a lighter note, I had 2 TCs failing (TLE) in CPCOMP for 70 point subtask. And I knew where the problem was. For my algo the scenario where there are no primes was a big bummer. What to do? I was like, ok…lets just simulate it. Pick random elements, compare them, add random edges. For connection of nodes we need < N edges, after that its just making cycles and useless stuff. So I start with Ans=N componenets. What are the chances that, if I randomly put edges by comparing random elements of array, I will miss a key edge which would reduce the answer? Well…quite likely. But perhaps a little over 60%? 30%? (Didnt do maths. Perhaps its some nCr in numerator and denominator).

Anyways, I give that a try, and well, one of the two passes XD. That again gives out a new info - that the passing TC has/might-have some randomness in it while other TC is very craftfully handmade. Perhaps a little more TL allowing me more simulations could have helped me pass that too, but then it was ok. We get new info we see where we can use xD. Eventually passed after a few hours.

The point, heuristics will be there where you get info per test file. If this, was instead like, you only get info about a subtask (and not of individual TCs in it), it will be much tougher. For Cookoff, its just a mishap twice a row. I am sure they’d make sure to try harder to frame stronger TC next time.

2 Likes
17

I tried divide and conquer and got green tick !
I haven’t used seg-tree for finding max element just a linear traversal. Thats it!
But
@taran_1407 I am asking this to you because you generally use JAVA and it would be helpful if you or somebody can tell me my mistake.

I have doubt why my first solution got RE but second solution passed.

Note : Just see solve() and dnc() function.
I changed global declaration of arr[] in the solution that passed. But any ways na() function always creates and initialises new array and takes input all array elements.

Can somebody tell me what was wrong in first solution ?

18

@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

19

@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.

20

Taranpreet very nice editorial. Thanks, keep doing great work.