I too was passing exactly the same testcase for a long time, then i notices that my code was not handling the case when there are colinear points on the polygon, I fixed that and maneged to AC all testcases except 2 which were giving TLE
1 Like
Hi
I am getting TLE for for two cases
Can someone check my code?
https://www.codechef.com/viewsolution/34388375
@pandey_ji1 Can you plzz tell me how condition 2 is not violated in this case??
How above approach going to work in this case.
Well… no. It’s more of the Simplification being tweaked a little. Let all the points that belonged to convex hulls which do not include the candle point, be called Floating Points . Turns out, the first/smallest convex hull that covers the candle point can be made non-convex to pass over all the Floating Points , without excluding the Candle Point.
can u clarify this part in more detail !?
so does we have to make the inner most hull non convex …so that it include the candle point …or we have to exclude the candle point and remain the inner hull convex ?!
After you get to the innermost hull, you are violating rule 2 because some green points are inside the yellow hull and the belong to no layers. To prevent this what we do is, simply connect all the green points and yellow points together to form a weird looking polygon as shown above, such that no point is left floating inside our last polygon. Of course, after this step the innermost polygon might end up becoming a concave one. Now we are not violating any rule, and the answer is simply the number of convex hulls.
1 Like
Yes. It is being violated. But we can tweak the last layer a little bit and satisfy the rule.
Simply connect (4, 7) -> (5,6) -> (5,7) -> (6,7) -> (5,2) -> (4,7). Now this is not a convex polygon, but that doesn’t matter. The question just says any simple polygon.
1 Like
Any simple polygon (may be concave ) but should not touch or overlap with other layers …m i rit !!?
Yeah that’s right. By overlap we mean the perimeters don’t intersect. And remember you are deleting the other hulls that you formed which do not contain the candle point (for this particular query).
Yep means after creating a concave polygon to satisfy the candle …will be the last polygon …or can be said as innermost polygon !!
@pandey_ji1 It was probably the best problem in Div 1.
Including illustrative images would have helped a lot to avoid the confusion the was created initially.
1 Like
Why do you consider the time complexity for generating the convex hulls to be O(N^2)? I implemented a modified version of the Graham scan algorithm as described in Geometry Algorithms TOC, which is O(N log N).
First sort the points by X and then Y in O(N log N). All remaining steps are O(N).
- Remove coincident points.
- Build a convex hull, sweeping across the points from lower left to upper right. (I modified the algorithm to keep intermediate points which lie along straight edges of the hull, to make the next step easier.)
- Remove all points which lie on the hull. They remain sorted without special action.
- Repeat from step 2, until there are none left.
You can see my solution at CodeChef: Practical coding for everyone
2 Likes
@bugger It’s always possible to construct a polygon which will contain a point inside it and rest as a part of it …if the point is not part of convex hull itself.
The innermost polygon which strictly contains the candle(i.e. the candle does not lie on one of its edges and is strictly inside it) can be transformed into a simple polygon by incorporating the floating points (which belong to all the inner layers from this point on) ,(5,6) in your case, removing that violation.
i.e. in this pic, the innermost layer in anti-clockwise fashion will be (5,2),(6,7),(5,6),(5,7),(4,7)
I think you are going though the whole (remaining) set of points each time you remove the points on the new hull. This, I think, makes each pass O(N). The number of passes is also O(N), so I think your solution is still O(N^2).
In theory one could reduce this to O(N log N) by storing the points in a red-black tree or similar, but the overheads might outway the advantage of this.
1 Like
Well, Graham Scan takes O(n \log{n}). That is not the issue. I used Graham Scan as well but the complexity was O(n^2) because I had to remove the points included in the convex hull from the set of all points (which I did in O(n^2).
Removing the points already included in the hull at each step is a linear O(N) operation, because the points are in a known order (see my solution). But I accept aberent’s reply, that we have to make a number of passes proportional to N, making the generation of all the hulls O(N^2).
1 Like
Inspired by your comment, and following my previous comment I have now created an O(N log N) solution, which is noticeably faster than my previous solution. To do it I am depending on the behaviour of python dicts. These preserve insertion order, yet deleting an element from a dict is O(1), so step 3 of the solution really is O(N). See CodeChef: Practical coding for everyone
Doing this and running using PyPy3 improves the performance from of task 10 (the slowest) from 1.95s to 0.58s.
1 Like