A week with Merlin

Codeforces Round 315 gave this week a great start on Monday (problems, results, top 5 on the left). Congatulations to Nikolay on his second Codeforces victory!

Problem D was a really nice opportunity for everybody to demonstrate their creativity. You were given 100000 lines on a plane, and needed to check if it's possible to pick 5 points such that every given line passes through at least one chosen point.

Even finding all pairwise intersections of those lines would not fit into the time limit, so we have to somehow reduce the search space. There are two main approaches to do it: randomized and deterministic. The main idea of the randomized approach is: if we just take two random lines from our set, how likely is it that they intersect in one of the 5 sought points? The main idea of the deterministic approach is: how many lines do we actually need out of 100000 to find one of the sought cover points or to determine that it's impossible to cover them with 5 points?

By the way (you might already know this, of course) for most programming contest problems you can submit your solutions after the contest ends, just for fun and to check your ideas - and that includes the problems I mention in this post, so feel free to take a stab at them without the contest pressure. Solving the problems after the contest ends is usually called "upsolving" in the Russian community, but the word doesn't feel right to me. How would you call it?

Google Code Jam 2015 Onsite Finals in Seattle was the main event of the week (problems, results, top 5 on the left, live stream recording). Gennady has continued his unbelievable victory streak well into the second year running - amazing talent and consistency! Bruce Merry has solved the same amount of problems including the most difficult one, but two of his solutions turned out to contain small bugs. Both of those problems, somewhat unusually for Code Jam, had large inputs that were substantially different from the small inputs, and thus one could not use the small's instant feedback to verify the solution for the large. That has cost Bruce dearly.

I was the author of problem A "Costly Binary Search", but I think problem E "Merlin QA" was the most beautiful in this round. Without the background story (which was very nice by iself), here's what the task boiled down to. You are given 100 8-dimensional vectors, and you're adding them in one of 100! possible orders, but with a small twist: every time one of the coordinates of the sum is negative, it becomes zero. Here's a 2-dimensional 2-vector example: if you have vectors (5, -2) and (-3, 1), then adding them in the given order yields (0, 0) -> (5, -2) -> (5, 0) -> (2, 1), while adding them in the reverse order yields (0, 0) -> (-3, 1) -> (0, 1) -> (5, -1) -> (5, 0). Your goal is to pick the order of addition that maximizes the sum of coordinates of the resulting vector.

I encourage you to try solving this problem by yourself for now, as the main idea is so beautiful, and I'll come back with the solution next week.

Google Distributed Code Jam 2015 Onsite Finals took place in Seattle one day later (problems, results, top 5 on the left). Once again had Bruce failed two of his large inputs, but this time he was so far ahead of the rest of the field that it hardly mattered. In fact, he could've failed one more large input and still win the contest!

Thanks for reading, and see you next week.