# Rocket Fuel competition: Rockethon

It might be a bit late, but note that there’s a contest Rockethon organized by the company Rocket Fuel on Codeforces. The contest starts in an hour (and the registration’s running until one minute before the end).

Too bad that it collides with Cook-Off. Why do people always miss that?

You can find out more about it here

UPD: The contest is over. Let me congratulate myself along with all who won a T-shirt. The worst place is not the last, but the 151st

And let me share my solution of D. It’s massive trolling: I made an O(N log N) with an incorrect idea (but which was able to pick just intersecting pairs), and then tried for every segment about 200 other segments intersecting it the closest to its midpoint. This is, of course, a wrong solution (and if expanded correctly, it’d work in O(N^2) time), but it got AC. Fortunately for me…

The correct part of the algorithm was just a sweepline. Let’s sort the vertical and horizontal segments (separately) by the x-coordinate (as given in the input); in a set, remember pairs (x-coordinate of horizontal segment end,number of this segment), and in a map, pairs (y-coordinate of horizontal segment,number of this segment). When we move a sweepline along the x-axis, we can add not yet added horizontal segments which start earlier than the sweepline, and then remove those which end earlier then it, using the combination of map and set - watch out for segments with the same y-coordinate, though. Also, we can find segments close to any y-coordinate quickly using the map.

6 Likes