Editorial request for Misha & Geometry (JUNE16)

editorial
1

It would be helpful if the author/Editorialist/admin could put up the editorial for the above problem.

8 Likes
2

Till we get an official editorial, here is my approach:

I basically implemented the following paper: https://www.ics.uci.edu/~goodrich/teach/cs164/notes/sdarticle-37.pdf

A general idea of the approach in the paper is necessary, so have a quick read of the basic algorithm, the data structures they use and in particular the “bridge” method.

First I load in all the queries and build a binary tree (“BST”) over the set of points that are added. The points reside in the leaves of the tree in sorted order. This allows me to avoid balancing the “BST”. Since I already knew all the “keys”, I had a guaranteed logN height. Instead of adding or removing nodes I just kept the count of the node in the “multi-set” from the question. A count of 0 just meant that the node is not a part of the tree right now.

The leaves contain individual points, and all the interior nodes contain the convex hull formed by points in both the children.

I won’t go too much into detail about how the hulls are merged, refer to the paper for that. One thing to note: I use the concept of upper hull and lower hull as opposed to left hull and right hull as it is in the paper.

Moving on, for the concatenable queues I used a Splay Tree. I got the general code off of wikipedia and implemented the merge and split functions myself. After some (READ: a lot) of debugging I was able to maintain the convex hull after the updates were made in log2n per update. This still required an O(n) calculation to compute the area.

I maintained the area using lazy propagation. Basically each node of the splay tree stores the area till that point. So on merging, all the nodes of the right sub-tree have their area increased by the area of the rightmost node of the left sub-tree. Similarly, for splitting, all the nodes in the right sub-tree have their area reduced by the leftmost node in that sub-tree. A single node has zero area. The first node (left-most) also has zero area.

For computing the area of the lower hull I just multiplied all the points’ co-ordinates by -1 and recomputed the area (adding it to the value computed for upper hull).

After another insane round of debugging, a somewhat messy but hopefully understandable AC: https://www.codechef.com/viewsolution/10445327

Hope this helps. I know its not a very detailed explanation but I am happy to answer any questions you have. :slight_smile:

12 Likes
3

@grebnesieh…

I was able to comprehend most of your explanation except for few points.

  1. “for the concatenable queues I used a Splay Tree”, could you please elaborate this point… I fail to understand the meaning of “concatenable queues”…& how is splay tree useful here?

  2. Is is necessary to maintain lazy node for calculating the area… can we do without it?

I would really appreciate if you could clear few of my doubts & thanks for compact yet to-the-point explanation.

4

@sharad07

  1. The concatenation queue is described in the paper. It is a data structure which maintains a given set of keys in sorted order. Further, you can split or combine any 2 such queues such that the sorted order is maintained. https://en.wikipedia.org/wiki/Splay_tree describes the join and split operation, which is made possible by the splay operation of the splay tree.

The bridge function in the paper splits two convex hulls from the children and then combines their left and right (split) parts to generate the hull of the parent.

  1. Not sure about any other way. That is the best (and only) way I could come up with. Maybe someone else can weigh in on this part.
2 Likes
5

Thank you for the help…

6

My solution in few words:

Convex Hull = Upper Convex Hull + Down Convex Hull

How to solve problem for upper convex hull? for down convex hull problems will be solve analogically.
Let’s we have only add queries. How to add point in upper convex hull in O(log N). Let’s maintain some data structure which can do two things with array(in array we will store points in order of convex hull):

  • Insert element in some position of array.

  • Erase some consequently subsegment from array.

Implicit treap/splay tree will be good for this.
When point is adding and it isn’t in convex hull, we should erase some subsegment of convex hull, we can do it with data structure which can do things above and insert new point in that place.

For solving all problem use divide-and-conquer by queries.
For each query “add point (x, y)” find nearest erasing of this point “erase point (x, y)”.
If this point won’t erased, let’s call that erase time = number of queries.
So we have for each point some segment [i; erase(i)], in this queries point will be “alive”.

Some pseudo code:

UpperConvexHull
Queries = {timeAdd, timeErase, point}

GO(L, R, Queries) {

Memorize states

int M = (L + R) / 2;

for Q in Queries

 if Q.timeAdd <= l && r < Q.timeErase

    upperConvexHull.addPoint(upperConvexHull, Q.point)

 elif Q.timeErase <= r || Q.timeAdd > r

    continue;

 else

    newQueries.add(Q)

GO(L, M, newQueries)

GO(M + 1, R, newQueries)

Restore Changes

}

Add point in convexHull will work in O(log Q), GO has complexity O(Q log Q), so total complexity = O(Q log ^2 Q)

That’s my code: http://ideone.com/HFUPg9

2 Likes