CHPLGNS - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vasia Antoniuk
Tester: Mahbubul Hasan and Sunny Aggarwal
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Minako Kojima

DIFFICULTY:

Cakewalk

PREREQUISITES:

Sorting

PROBLEM:

There are N polygons such that for each pair of polygons one of them lies strictly inside the other. Output for each i how many of the given polygons lie inside the ith polygon.

SHORT EXPLANATION

Observe that the if polygon P_j lies inside P_i then the maximum x cordinate of a point in P_i is greater than that of P_j. Sort the polygons based on the maximum x coordinate in decreasing order. If the i^{th} polygon appears at the j^{th} position in this sorted order, then there are N - 1 - j polygons that lie inside the i^{th} polygon.

EXPLANATION:

This editorial is in a different format than usual. The solution is presented as a conversation between two coders. Thanks to Pravin Dhinwa for the idea. (Note: Discussion between coders during the contest is considered cheating and hence not recommended :slight_smile: )

So given the constraints what type of arrangements are possible/not possible?

Well, there can be no intersection so I guess the polygons will be one inside the other.

But what about the solution?

All I can think of is: For each polygon i, loop through all other polygons j, somehow find whether j lies inside i or not and count all such j

This is a correct algorithm but it will take O(N^2) time. We have to optimize it a bit.

How about this optimization: if polygon P_j lies inside polygon P_i then we know that P_i can’t lie inside P_j (Since there are no intersection) and vice versa. So, if we know the relation between P_i and P_j then we need not check again for P_j and P_i.

This reduces the work done by half, but still won’t be enough. What about some more optimization.

I can’t think of any

How about this: If P_j lies inside P_i and P_k lies inside P_j then P_k also lies inside P_i. In other words this relation is transitive.

Great! But wait, how do we know if a polygon P_j is inside polygon P_i?

Well, I saw a few images. If the area of polygon P_i is greater than the area of polygon P_j then P_j lies inside P_i. Whoa, I think we are very close to the solution.

Thats brilliant. And I have another algorithm using this: First find the polygon with maximum area. We know that all N - 1 other polygons will lie inside this polygon. Now we do the same step for the remaining N - 1 polygon

But this will still take O(N) time for each step and there are N such steps for a total of O(N^2) time. And I have not even included the time for finding the area. But I noticed one thing, if we list out the maximum area polygon found at each step, they will be in descending order.

Eureka! So we are basically sorting. And that can be done in O(N log N). We sort based on the area and also keep track of which polygon has that area so that we can update the answer for that polygon

Yeah we have the solution. Let us implement this.

Huh, you implement. I don’t feel like googling and copy pasting the code for finding the area of polygon. There should be some easier way for this

I think there is! I observed the valid figure again and noticed that instead of the area, we can use the highest x coordinate of any point of the polygon for comparison. If the highest x coordinate of P_i is greater than that of P_j then that means P_j lies inside P_i. So, we have finally solved this. O(N log N) algo.

Don’t forget that we have to find the max x coordinate for each polygon so the complexity will be O(M + N log N) where M is the total number of points in the test case.

Yeah. Pseudo code:

polygons - a list of tuples
for each polygon i from 0 to N - 1:
    input mi
    Input mi points and find max x coordinate max_x
    add the tuple (max_x, i) to polygons

sort polygons in decreasing order of max_x

ans - An array of size N to store the answer
for each j from 0 to N - 1:
    Let the ith tuple in the sorted polygons be (x_i, i)
    All the polygons that come after this in the list lie inside this polygon. There are N - 1 - j such polygons.
    ans[i] = N - 1 - j

Time Complexity:

O(M + N log N) where M is the total number of points in the test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

5 Likes

Highest x-coordinate! Wow, never thought of that :slight_smile:

I implemented it using area and sorting. O(M+NlogN)
Solution

2 Likes

Solution proposed in this editorial is, sure, correct when “For any two polygons P1, P2, either P1 lies inside P2 or vice versa”, as it was stated in the problem statement. There were also, at least, two different solutions: (1) sort the polygons based on their areas (2) sort the polygons honestly comparing for the polygons P1 and P2, whether P1 is contained withing P2 - it easy to do with ray-tracing approach with the given constrains. The approach (1) gives correct solution and there is no overflow problems. The approach (2), with which I was unlucky to approach the problem at first, fails on the Test Case #9, showing that “For any two polygons P1, P2, either P1 lies inside P2 or vice versa” constrain is violated in that test case. Now I’m quite sure about it, as I re-implemented my solution several times, using integer and float-point arithmetic, and a bit different tactics to use the ray-tracing approach. Also such approach showed me that in the Test Cases #### 4 and 10 some of the polygons touch each other (i.e. there are such polygons P1 and P2, that, at least, some of the vertices of P1 lies on the edges of P2).

Unfortunately, having my Karma=1 I was not able to ask about it during the contest: all my attempts to comment on the problem page were lost somewhere in moderation queue, and also I was not able to start a new thread in this forum. Anyway, now, though I’m pretty sure I’m right about the problem with the Test Case #9, I’d like to have the confirmation of my thoughts from the authors/other participants.

We could sort any of the point x-max, x-min, y-max, y-min. Initially I got partial marks when I sorted using y-max and got full points using x-max

But now when I see the MY submission page both the solution are accepted

Finally there are correct test cases… :slight_smile: :slight_smile:

Please review my WA solution and help me undestand what is wrong.
I am using java.awt.Polygon and java.awt.Rectangle.
Idea is to get the rectangle bound from the polygon and compare rectangle r1, r2 as

r1.contains(r2) ? 1 : -1;

What is wrong if I consider the absolute maximum value of all the coordinates for each polygon rather than considering the maximum of x-coordinates? Can you give a case as in which this fails? The reason why I used this logic is since, if a polygon is inside other, it cannot have the maximum coordinate value either x or y, more than that of the outer one. Please tell me when this goes wrong? I have taken abs(coordinates) before comparison.
Please tell me what’s wrong with this logic or my solution.
http://www.codechef.com/viewsolution/7227847

@rajavineel: Your solution looks not for the maximum of abs(x-coords), but of for the maximum of both x and y ones.

Please tell me whats wrong with this solution ?
http://www.codechef.com/viewsolution/7235511

@rajavineel , you and me were doing similar mistake. FORGETTING TO CLEAR THE VECTOR !!! :slight_smile: :slight_smile:

The error was that I did not clear the vector. Thanks sumitjha4321 for pointing the error. It works now.

My code gives AC for 6 cases, and WA for 9. I cant figure out why. Im finding area and then sorting wrt to area.
Any help?
my code - http://ideone.com/gCORiI

EDIT - converted int to long long… got AC. FML

@birdofprey. Having similar issues. I was using point-in-polygon test by finding the winding number. Actually, I did this twice actually with two very different algorithms (one by taking total angle sum, one by tracking movement between quadrants), but got AC on only half of the test cases – same WA for both algorithms, which seems suspicious. Highly suspect bad test cases.

@sid_sp123. Gets the bounding box of this Polygon. The bounding box is the smallest Rectangle whose sides are parallel to the x and y axes of the coordinate space, and can completely contain the Polygon.

since is a rectangle, there can be a polygon that lies inside this rectangle, but lies outside the polygon. your code would fail there

I used the logic that the perimeter of the inner polygon is less than the perimeter of the outer rectangle, and as usual sorted it and found out the answer

can anybody point out error in my solution?? i used the same approach as described in this tutorial(area sorting) but getting ac partially :frowning:

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

calculating the max area approach might fail if do not consider origin as the centre of each polygon.
lets say the triangle given in problem have the same area but is shifted so that it comes out of both the polygon.
In that case this method fails according to me… please correct me if i am going wrong somewhere…

I solved this problem by calculating area using the shoelace formula and then sorting, it managed to pass all test cases although I think the editorial solution is better.

In the question, are they assuming that the centre or centroid of the polygon lies on the centre?

@njr07121977 You are wrong: perimeter of the enclosed polygon does not have to be smaller than perimeter of the enclosing one. If this solultion passed, it means that test-cases were poorly prepared (and as it is stated in my and some other comments above, it is highly probable, that some test-cases were just wrong and violated problem statement).