This week in competitive programming

Just two rounds happened this week, both on Wednesday. The first was TopCoder SRM 642 (problems, results, top 5 on the left). Given that the total time between the start of the SRM at 5am Moscow time and the end of the following Codeforces round at 9:30pm Moscow time was 16 hours 30 minutes, it was quite hard to participate in both while maintaining a healthy sleep schedule, so I've passed on the SRM :) Nevertheless, anta showed that my fears were unfounded by winning the SRM and placing fourth in the Codeforces round - great job!

Codeforces rounds with problems by Endagorion are becoming a trademark of their own because of interesting and diverse problems, and Round 283 was no exception (problems, results, top 5 on the left, my screencast). Baz93 claimed the first place thanks to the super-fast solution for problem D. You were given two (not necessarily convex) polygons, each rotating around a point with the same angular speed in the same direction (those rotation centers could be different for the two polygons, and could be outside the corresponding polygon), and needed to determine whether they will ever intersect or touch. Each polygon had at most 1000 vertices. The problem requires both a geometrical insight, and some computational geometry mastery - can you see the insight?

I was going to describe the solution to the Open Cup problem discussed in last week's summary, but I was beaten to it in comments by +Ilya Kornakov and +Andrey Kolosov, so you can check them out instead :) The other problem mentioned in last week's summary, about counting triangles containing the origin, was solved in NlogN using the following insight: instead of counting triangles containing the origin, let's count the triangles NOT containing the origin. Each of those triangles is contained in some half-plane containing the origin, so if we rotate the half-plane slowly, then every time a new point arrives in the half-plane, we should increment the result by (n-1)*(n-2)/2, where n is the current number of points in the half-plane, thus accounting for all triangles containing the newly arrived point.

Thanks for reading, and check back next week!