PROBLEM LINK:
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 
)
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.
