SEABAL - Editorial

[gamabunta]

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

PREREQUISITES

Segment Tree, Fenwick Tree

PROBLEM

You are given an ordered list of N integers that represents the number of ballons at each position.

Also, you are given M pairs of integers that represent ranges, or segments, within [1, N].

You perform K pricks and burst K ballons. It is guaranteed that you never prick at a position without a ballon.

• Initially, you prick at x₁
• Let the number of segments out of M that contain no ballons now be ans₁
• Next, you prick at x₂ + ans₁
• Let the number of segments out of M that contain no ballons now be ans₂
• Next, you prick at x₂ + ans₂
• and so on

Find all the answers { ans₁, ans₂, … ans_K }.

EXPLANATION

The restriction to find the previous answer before processing the next query means that primary focus of this problem is to optimize the cost of making a query.

It greatly simplifies the ideas involved in solving this problem if we visualize the M segments as points on the 2D coordinate plane

• The start point of a segment is the X-coordinate
• The end point of a segment is the Y-coordinate

Of course, we maintain the number of ballons at each position. Now lets consider the query which performs a prick at position P. There are two cases to consider

There are several ballons at P

Pricking a ballon will introduce no position with 0 ballons. Since we need to calculate the number of segments that contain no ballon, this case is uninteresting. It doesn’t change the answer to be printed.

There is only 1 ballon at P

After we prick this ballon, there will be no ballons at P. This case is interesting. We can now consider the segment [left, right] where

• left ≤ P
• right ≥ P

and all the positions between left and right inclusive contain no ballons. Any of the M segments that lie completely inside [left, right], inclusive, should be counted from now onwards.

We can visualize the range [left, right] also as the point (left, right) on the 2D coordinate plane. We wish to consider, from this query onwards, all those points (from the set of M points)

• The X-coordinate ≥ left
• The Y-coordinate ≤ right

In other words, points which are on the bottom right quadrant if we consider (left, right) as the origin.

Before we proceed to solve the problem of efficiently reporting (and deleting) points that lie on the bottom right quadrant of (left, right), you should know how to calculate (left, right).

Fenwick Tree

You can store the number of ballons from the start of the list to the current position, in a Fenwick Tree. The prick operation can update the count through the Fenwich Tree in O(log N) time.

You can find the left-most position with the same count (meaning, no ballons in between) by binary searching on the Fenwick Tree in O(log² N) time.

Similarly, you can find the right-most position as well.

Refer to the Setter’s solution for an implementation of this idea.

Ad-Hoc

If you don’t prefer using Fenwick Tree, you can maintain the left and right pointers at each position.

These pointers are updated as the number of ballons in the neighbors reduce to 0.

This idea is implemented in the Tester’s solution. The complexity of this approach is amortized O(1), as opposed to O(log² N) above for each query.

Segment Tree

Now we have changed the problem to the following subproblem

You are given M points in 2D space. Build a data structure on these points to efficiently process updates of the type

• Find the number of points on the bottom right quadrant of a query point (l, r)
• Delete all the points on the bottom right quadrant of a query point (l, r)

We can further simplify the above queries as follows, and they will still fulfill our purpose

• Find the point with the smallest Y-coordinate which is on the right of (l, r)
• Delete that point

What we have here is the classical problem of Range Minimum Query (RMQ).

We can assume that we have an array of Y-coordinate values in the order of the sorted X-coordinates. For a query point (l, r), we wish to find the minimum value in the range (l, N). If this minimum value is not more than r, we have another answer!

Along with the minimum values, we must also store the index. This allows us to perform the delete easily.

Updating the Y-coordinate at that index to an arbitrarily large number is enough to delete the point. This update of course also updates the Segment Tree to further handle more RMQ.

The amortized time spent for each query is O(log N).

Together with the calculation of the parameters of this query, the total time spent for each query is O(log² N + log N) or simply O(1 + log N) by using the Ad-Hoc method.

CODE COMMENTARY

For the sake of discussion above we have ignored a degeneracy - there may be several points with the same X-coordinate.

There are two ways to handle this case.

Setter’s way

You can maintain link lists of Y values in increasing order for each unique X value. You simply edit the Segment Tree’s update step a little. Instead of changing the Y-coordinate to an arbitrary large number, you use the next higher Y value.

Tester’s way

For the same X-coordinate, sort the points in increasing order of Y-coordinates.

One doesn’t have to worry about handling anything in this case. The described algorithm should work out of the box.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

[tyrant]

@gamabunta: Setter’s solution link was broken, could you please fix it? Thanks in advance.

[deepai_dutta]

I din’t understand this part…
You can find the left-most position with the same count (meaning, no ballons in between) by binary searching on the Fenwick Tree in O(log2 N) time.
Similarly, you can find the right-most position as well.
Could you please elaborate it a bit??

[rishul_nsit]

In case pricking at a position P reduces the number of balloons at P to zero, you can find the leftmost position in the array which has zero balloons by applying binary search starting from P on the left of P and the rightmost position in the array which has zero balloons by applying binary search starting from P on right of P.

[honeyslawyer]

i cnt open the setter’s solution

[lutyj]

If you don’t prefer using Fenwick Tree, you can maintain the left and right pointers at each position.
These pointers are updated as the number of ballons in the neighbors reduce to 0. This idea is
implemented in the Tester’s solution. The complexity of this approach is amortized O(1)

Why maintain these pointers at each position? We only need them at the ends of each zero segment. It’s simpler and also gets us O(1) guaranteed complexity.

[dtb]

I don’t understand this approach. Somebody please explain the adhoc/tester’s solution more.

[alex_2oo8]

I have a little bit different solution with Segment Tree:

I will call Segment Tree as ST, range - one of given M ranges, segment - one of ST nodes interval.

We can split each given range into O(logN) segments from our ST. For each segment from ST we can easily determine when this whole segment is empty (just storing a sum into each node). So, for each given range we just want to know, when the last of O(logN) segments will become empty.

It can be also quite easily solved:
For each node of ST we will maintain a list of ranges, which have to be updated, when the whole segment will become empty. First of all, we will add the ranges to the ST, i.e. let split the range into K segments from ST and add this range to the list of each of these K nodes, for each range we will also remember the number K (cnt[range_i] = K).

Then we will process the queries:
Each query will be just update to the ST - decrease value in the Pth box. When some segment will become fully empty (i.e. sum on this segment = 0), we will iterate over all the ranges from this nodes list and decrease the value of cnt[range_i] for them. When some cnt[range_i] will become a zero - we have found a new empty range (i.e. ans++).

Here is my implementation, but I store in ST 1, if i-th box is empty and 0 otherwise: http://www.codechef.com/viewsolution/2420792

PS Sorry for my bad English, but I hope that it is possible to understand

[notimesea]

Tests are rather weak, There are a lot of solutions,(e.g. this solution(not mine) http://www.codechef.com/viewsolution/2512914) have O(mk) worst case complexity, but one of the best time of execution. Test: just do all segments [1, n]. All a[i] = 1, and make queries 1, 2, 3, 4 and so on.

[n2n]

Basically, for each box, you keep 2 pointers pointing to the boxes which contain non-zero number of baloons one to the right and another to the left. When the number of baloons in some box reduce to zero, you update the pointers. Similar data-structure and algorithm is used in many malloc/free implementations. My implementation: http://www.codechef.com/viewsolution/2501939

[styagi280994]

I did it using disjoint sets :).
Here is the link http://www.codechef.com/viewsolution/2526567

[drazen]

I’ve used a slightly different approach, with k-d tree to index intervals as points (start, end). Additionally each node in the tree stores cumulative count of points beneath it. Then, for each new consecutive segment of zero balloons (L,R) query the tree for number of points inside rectangle (left,right,bottom,top) = (L,R,L,R). This yields O(MlogM + N + Ksqrt(M)) solution, which runs in 0.6sec.

---

[EDIT] More details, as reply to @bondoc73

• Build a k-d tree, store each interval as a 2D point (x,y) = (start, end)
• If we want to find number of intervals that are completely within bounds (lower, upper), we query the tree for number of points such that x >= lower AND x <= upper AND y >= lower AND y <= upper, which translates to number of points inside rectangle (left,right,bottom,top) = (lower, upper, lower, upper). Thus, a query CountIntervals(LeftBound, RightBound) is equivalent to CountPointsInRectangle(LeftBound, RightBound, LeftBound, RightBound)
• As described in the editorial, we keep track of sequences of empty boxes. When we pop a balloon at position P, if it was the last one in the box, we have added a new empty box to the sequence. Assume that P is just in between previously empty box sequences (Left, P-1) and (P+1, Right). By inclusion-exclusion principle, we update result as follows:
  res += CountIntervals(Left, Right) - CountIntervals(Left, P-1) - CountIntervals(P+1, Right)

You should be able to work out cases when there are no empty box sequences on left or right side of P.

[bondoc73]

Interesting idea @drazen … Please can you explain you code?

[MarioYC]

I got a different solution by doing merges of binary search trees (treaps in my implementation), by using the trick of always merging into the tree with more nodes, so each node is merged O(lgn) times at most.

http://www.codechef.com/viewsolution/2486038

[bondoc73]

Thx a lot. It’s now crystal clear

[darpanthedude]

@gamabunta the link to the setters solution is still broken. Please fix it.

[forthright]

I solved it by doing exactly as it said in the editorial ( the setter’s version ). Since the Setter’s solution link is broken, maybe this would help. I commented it as much I could: http://www.codechef.com/viewsolution/2592629

[kq_viet]

Setter’s solution is broken

[k0stia]

Could you say what is the time complexity of your approach?