Tuesday, May 26, 2015

A week when tourist becomes retired (not really)

ACM ICPC 2015 World Finals was the event of this week (problems, results, top 5 on the left, my twitter commentary, full video recording). Congratulations to ITMO on the amazing victory and 13 solved problems, and to all other medalists for outstanding results! Both Moscow State University and University of Tokyo looked to be leading the contest at times, but ITMO solved three in the last hour to finish in a clear first.

Here's one of the trickiest problems of the finals - problem K: you're given an undirected graph, and need to find all numbers k such that it's possible to color all of the edges in the graph with k colors in such a way that every simple cycle in the graph is colored evenly: has equal amount of edges of every color. It's mostly a mathematical problem, but has both a very nice statement and a very nice solution, which you can find in my twitter. The video recording also contains analysis for all problems, here are the direct pointers.

Top three teams are not eligible to compete next year (except maybe one person from University of Tokyo?..), please share any details about other medalists returning or other upcoming strong teams! Anyway, the competition is wide open, and the finals will take place in Phuket, Thailand.

Yandex.Algorithm.2015 Round 1 happened on the weekend (problems requiring login, results, top 5 on the left). The problemset was quite unusual with 5 problems of roughly the same difficulty, and one easier problem (problem F), thus paving the way for very diverse results at the top. I've taken great care not to submit incorrect solutions, writing a stress-test in 3 problems out of 5 I've solved. I was lucky nobody managed to solve all six without those precautions.

One of the more standard problems was problem B, where you were given 1000 points on the plane with weights, and asked to separate all points with a straight line into two halves with as close total weights as possible. The stress-test I've implemented here was a bit non-standard, so I want to share it with you. The O(N2logN) solution for this problem involves iterating over one of the points that will be "very close" to the dividing line, then rotating the line around this point keeping track which points are on one side and which points are on the other side. I've made my solution rotate the line three full circles around each point instead of one full circle, and assert that we get the same result after rotations that differ by a full circle, and then just ran it on randomly generated testcases - finding a bug in the code that manifested as inconsistencies between two rotations that are essentially the same (the bug was using the unsorted array of points instead of the sorted one), and submitting the correct solution afterwards.

Thanks for reading, and check back next week!

Wednesday, May 20, 2015

ICPC World Finals 2015 and Twitter

I've been trying to put my thoughts together to tell you something about the World Finals going on right now in Marrakech (photo on the left is from the official photo archive).

ACM ICPC always gathers really passionate and professional people, and together they do amazing things. Be it contest judges, event organizers, the analytics team or the sponsors from IBM - everybody always goes out of their way to make the event better than ever. This year I have another confirmation of this with the new ICPC Live team which are almost all my good friends (more details). A group of people who to the best of my knowledge have never been involved with broadcasting and live sports coverage, are getting ready to bring the programming contest live coverage to a new level - tune in tomorrow and see for yourself!

Of course, this passion is also seen really well in the participating teams themselves. The team from my alma mater, Moscow State University, have been preparing really hard to try and beat the overwhelming pre-tournament favorite, SPb ITMO. They've solved a lot of training contests and are paying attention to every little detail to make sure they do their best tomorrow. The attention to detail reaches funny heights sometimes: the rumor has it, they've chosen different T-shirt colors this year (gold on dark red instead of the traditional red on white) because the old color combination always resulted in second place for good MSU teams, not the first place - this happened four times. This is just a superstition, but they have of course did the more serious preparation very well, too. Good luck Gleb, Victor and Mikhail!

One might say that in both examples I'm praising my friends, and that's no surprise. I think that I'm writing about my friends because I know the most about them, but I'm pretty sure that almost everybody else involved with ACM ICPC has similar stories to tell about their friends - and that's how a great community is formed! Feel free to share your stories in comments.

I've realized that I don't have enough courage and energy to write a live blog about the World Finals tomorrow, so I've set up a Twitter account that I'll use to post some news and comments instead. Please follow :)

Monday, May 18, 2015

A calm week before the storm

This week was very calm compared to recent ones, with just one competition: TopCoder SRM 659 in the middle of the night on Wednesday (problems, results, top 5 on the left). Three "target" coders participated in the match: UdH-WiNGeR held the first place after the coding phase with the fastest solution for the 500-pointer, but his solution for the 250-pointer failed; Endagorion was almost as fast, but that was only enough for the second place because RAVEman found three successful challenges to squeeze out the victory. Congratulations Anton!

Many top-level competitors are now in Morocco to participate in, judge, analyze, broadcast, or just watch the ACM ICPC World Finals. The participating teams, ordered by the rating of the highest member, can be found on Codeforces, and there will be live broadcast of the competition on Wednesday on ICPC Live. The trend in the programming competition world is exploring different formats and new types of problems lately, while ACM ICPC did not change much in the past years. Are we going to see some new types of problems (interactive problems, random-input problems, or maybe something completely new) this time?

In the next three days, I will also try to share some ICPC news and information that is not covered via the official channels, so stay tuned!

Saturday, May 16, 2015

A week with division by zero

TopCoder SRM 658 continued the recent trend of Tuesday rounds (problems, results, top 5 on the left). The hardest problem gave one the most freedom, as it admits several different approaches: consider a bipartite graph with equal number of vertices in both left and right parts. You need to find a non-empty matching (set of edges with no common endpoints) in this graph such that for all vertices covered by the matching in the left part all their neighbors are covered by the matching in the right part. In other words, there should be no way to replace just one edge in the matching with another edge with the same left end. If you’ve already solved this one after reading it, here’s a much harder follow-up from the problemsetter, cgy4ever: what if the total number of vertices in the left and right parts are not necessarily equal? I don’t have a solution for the follow-up yet.

Codeforces Round 302 took place two days later (problems, results, top 5 on the left). Problem D turned out to be the trickiest one, with just 73 solutions accepted for 352 contestants that submitted it. Of course, that also gave rise to a plenty of challenge opportunities. Let me describe one of the more subtle bugs, but first, let’s remember the problem statement.  A green coloring of a rooted tree is such coloring of its edges into green and white such that every path from a leaf to the root contains at most one green edge.  Given an unrooted tree, how many green colorings exist for each possible choice of the root?

When the root is given, counting green colorings can be done via quite standard dynamic programming. In order to solve the problem for all possible roots many contestants including myself updated the total number of colorings as we move the root from a vertex to one of its neighbors. It’s actually not very hard to see how this number should be updated, but it comes with a twist: such update involves dividing the old number by one plus the number of valid colorings for a subtree, and since we’re computing the answer modulo 109+7 (as requested by the problem statement), division is not always possible!

When one implements the above solution in the most straightforward way, it might fail if a subtree of the input tree has exactly 109+6 possible colorings, or more generally k*(109+7)-1 for any positive integer k. It doesn’t look extremely likely to happen at random, but given the existence of challenges on Codeforces, many people were bound to spend some effort creating such testcases, and thus we’ve actually got plenty: some are described in the post-match discussion. Can you come up with such testcase without reading the discussion?

TopCoder Open 2015 Round 1C was the last chance to hop on the TopCoder Open train (problems, results, top 5 on the left). krijgertje, who was once ranked fourth overall but has stopped competing regularly, came out from retirement and claimed the first place thanks to fast solutions and some challenges - congratulations!

And finally, Google Code Jam 2015 Round 1C has determined the final 1000 qualifiers for this year's tournament (problems, results, top 5 on the left, analysis). Congratulations to Klockan on solving all problems just under 40 minutes, and good luck to all 3000 qualifiers in Round 2!

Thanks for reading, and check back tomorrow for this week's summary :)

Saturday, May 9, 2015

A week almost forgotten

TopCoder SRM 657 (problems, results, top 5 on the left) happened very early on Tuesday. The hard problem, despite being conceptually harder, was more standard, while the medium problem required more creativity - as a result, I've spent more time on it, and had to resubmit my solution because of a bug I've found through stress-testing against a brute-force solution on random testcases. Here's the tricky problem: what's the maximal integer that always divides the product xd0*(x-1)d1*...*(x-n)^dn, irrespective of value of x (the only thing we know that x is an integer)? You are given n and di as inputs, n is up to 10000, each di is between 0 and 9, inclusive.

And of course, congratulations to ainu7 on his fourth SRM victory!

Google Code Jam 2015 Round 1B was the Saturday's contest (problems, results, top 5 on the left, analysis). The problems were quite non-standard this time, and one could easily miss an idea and get stuck. However, solving any of them in full plus one other easy input was enough to qualify, so the best strategy was to skip over problems you're stuck in. Congratulations to vepifanov on not getting stuck at all and solving all three in just over an hour!

VK Cup 2015 Round 3 happened exactly 24 hours later (problems, results, online mirror results, top 5 on the left). The rating favorite team Never Sorry faced a strong challenge from team BananaIsBack, and made the deciding challenge just 10 minutes before the end of the contest. Congratulations to both teams on the amazing competition!

It's been a long time since I posted solutions in addition to problem statements, so let me try to repay that debt :) Two weeks ago, I've posted two problem statements, here's the first one. Several duathletes are competing in a swimming+running duathlon. You know the swimming speed and the running speed of each duathlete, but you don’t know the swimming distance nor the running distance. Which duathletes could win or at least share the first place for some combination of swimming and running distances?

Let the r be the running speed of a duathlete, and s be her swimming speed. Let R be the total running distance, and S be the total swimming distance. Then the total time she's going to spend is R/r+S/s. We need to see if there exist R and S such that this value is maximum over all duathletes. Let's rewrite the above expression as R*(1/r)+S*(1/s) - now we see that it's a scalar product of two vectors: (R,S) and (1/r,1/s), which we can recall to be equal to the length of vector (R,S) times the (signed) length of the projection of vector (1/r,1/s) to the line containing vector (R,S). Since the length of the vector (R,S) is going to be the same for all duathletes, we've essentially reduced the problem to the following geometric one: among given points (1/r,1/s) on the plane, does there exist a line such that projecting all points to this line will result in the given point being the first on the line? Now it's not hard to see that we need to find the convex hull of points (1/r,1/s), and then take its part that corresponds to lines where both R and S are positive.

I like the solution for the other problem posted two weeks ago even more. The problem was: you are given n 4-tuples of points on the plane, and m rectangles with sides parallel to coordinate axes. For each rectangle, you need to check if it contains exactly 2 points from each 4-tuple. In other words, if there’s at least one 4-tuple with 0, 1, 3 or 4 points inside this rectangle, then its answer is “No”, otherwise it’s “Yes”.

The statement is a bit unusual. What would be a more usual one? For example, we might be asked to count the number of given points inside each given rectangle - that one is a standard problem solved via iterating over points and rectangle boundaries in increasing order of one coordinate, and using a Fenwick tree over the other coordinate. Even if each point has an associated weight, we can find the sum of weights of the points inside each rectangle using exactly the same approach.

However, we're not interested in the sum of the weights of the points - we need to know almost exactly which points are inside which rectangle in order to tell if the condition from the problem statement is satisfied. Here's the crucial step: let's assign the same weight for the points inside each given 4-tuple, and different weights for the points from different 4-tuples. Then the fact that we need to have exactly 2 points from each 4-tuple corresponds to exactly one sum of weights. But some other sets of points might have the same sum of weights, too, so we might have false positives. But it's not hard to see that if we pick the weight for each 4-tuple randomly, then the probability of an incorrect set having the same sum of weights as the correct set is very small - essentially, a sum of several random numbers should be zero, and that's unlikely. So we can simply pick random integer weights up to 232, and then look for rectangles with an appropriate sum of weights inside!

Finally, one week ago I've posted the following problem: you're watching a robot that performs a program of given length L in an infinite cycle on a Cartesian plane. Each of the L steps of the program is a move in one of four cardinal directions, and after the last step the robot continues with the first step again. You're given the locations of the robot at different times (more precisely, at most 105 times, each time is at most 1018), and need to restore at least one possible cyclic program of length L that would lead to the robot appearing in given locations at given times, or report that there isn't any.

The first step in solving this problem is to split the two-dimensional problem into two independent one-dimensional problems. If x, y are the Cartesian coordinates of the robot, let's define p=x+y and q=x-y. It's not hard to see that moving in one of four cardinal directions corresponds to changing both p and q by +1 or -1, and we can achieve any combination of those changes. Because of this, we have to restore a cyclic program for p and a cyclic program for q, and then combine them to get the answer for the problem.

The one-dimensional problem is naturally easier to analyze. Let's say that the value of coordinate p after i-th step of the robot is pi, and p0=0. Since the robot's program is periodic, we have pi+k*L=pi+k*pL. That means that we essentially have L+1 variables, each two consecutive variables must differ by exactly 1, and we have a set of equations of form pi+k*pL=t. If we know the value of pL, then each of those equations has just one variable, and we can determine the value of each variable that is present in at least one equation, and reconstruct the values of variables between the known ones by gradually adding or subtracting 1. How to find pL? Well, if there's at least one variable that appears in two different equations, we can determine pL from that system of two equations. And when there's no such variable, then the fact that variables pi and pj differ by at most |i-j| gives a set of boundaries on pL. It's not hard to check if a set of boundaries is consistent, and if yes, find any value of pL that satisfies those boundaries. Having found such pL, we can reconstruct all variables from equations, and then reconstruct intermediate variables by adding and subtracting 1. It can turn out to be impossible only if some pi has a different remainder of division by 2 than i - but in that case it's not hard to see that there's no solution.

Thanks for reading, and check back soon for next week's summary - hopefully you won't have to wait until next Saturday :)