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 :)

Thursday, April 30, 2015

A week where Open Cup ends

Another very busy weekend in competitive programming started with Russian Code Cup Qualification Round 2 (problems in Russian, results, top 5 on the left). The current ACM ICPC World Champions have occupied the two top spots, and big congratulations to Pavel for solving all problems!

TopCoder Open 2015 Round 1B took place later on Saturday (problems, results, top 5 on the left). Since all coders with "red" rating that have participated in at least one SRM in 2015 got automatic promotion to Round 2, the top of the scoreboard consistent exclusively of somewhat retired contestants. Seyaua has overcome several coders with much higher rating to claim the victory - great job!

Open Cup 2014-15 Grand Prix of East and West happened on Sunday (results, top 5 on the left). The same problemset will be used for an upcoming online contest at Timus, so I don't want to go into detail about the problems - will do my best to come back to them later.

Codeforces Round 300 wrapped up the weekend's competitions (problems, results, top 5 on the left). With 8 problems in the round, it wasn't easy to get them all, and thus people who opted to spend more time on hacking were rewarded - congratulations to Bruce on squeezing out the first place! I've decided to do both hacking and solving the last remaining problem, and in the end was not so successful in both directions. There's a popular Russian saying to that respect, which the Internet suggests sounds as "between two stools you fall to the ground" in English :)

Here's the problem I couldn't get during the round: 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.

Another big event took place on the weekend: the 24-hour programming session with live video and commentary by Mimino (event page), where he explained solutions to Project Euler problems as he solved them. Only the first 4 hours of the recording seem to be available now.

Thanks for reading, and check back next week for the solutions of the problems I mention here and in last week's summary!

Thursday, April 23, 2015

A week with different analysis approaches

Before we turn to this week’s events, let’s come back to Qualification Round of Google Code Jam from last week that I’ve somehow forgot to mention (problems, results, top 5 on the left, analysis). The round has lasted for 27 hours and the time of submissions did not matter for qualification, but some contestants still tried to be as quick as possible – congratulations to kyc on being the fastest!


The Code Jam has continued this week with Round 1A (problems, results, top 5 on the left). This time one needed to be fast or solve all three problems in order get into the top 1000 and advance.  Sergey ‘Burunduk1’ Kopeliovich has demonstrated really impressive speed by solving all three problems in just 23 minutes – awesome job!

There were also plenty of other contests this week. On Tuesday, Codeforces Round 299 (problemsresults, top 5 on the left) challenged everybody with some tricky-to-get-right problems – a lot of solutions have failed the system test, including two of myself. Problem C has highlighted one of the beautiful, if a bit standard, ideas of transitioning an algebraic problem into a geometric 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?


VK Cup 2015 Round 2 was also hosted by Codeforces (problems, results, mirror results, top 5 on the left). The “Never Sorry” team took matters in their own hands this time, being the only team to solve all problems and adding 5 challenges on top of that – amazing! Of course, this is still an early round and the real battle will be at the onsite competition in July.

SRM 656 was TopCoder’s event of the week (problems, results, top 5 on the left). baklazan4247 was the only contestant able to solve the hardest problem correctly, but that was not enough for the first place as he skipped the medium difficulty problem, and xudyh did not, solving it in just 8 minutes and earning the 3000+ "target" rating as the result - congratulations! He seems to have a blog in Chinese telling about his programming contest experiences, but the auto-translated version doesn't seem terribly accurate :)

And finally, the Open Cup Grand Prix of Three Capitals took place on Sunday (results, top 5 on the left). Problem F is a very nice example where using randomized algorithms is much more appropriate than deterministic ones. It went like this: 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”. Can you see how randomness makes this problem easy? On the other hand, can you see a deterministic solution?


Also last week in an offline discussion with Maxim Buzdalov, we’ve brought up the following topic: what’s the best way to do problem analysis at ACM ICPC training camps? The Russian “golden standard” of Petrozavodsk is to use chalk and blackboard to explain the main idea of the problem solution on the stage live, also recording the explanation on camera for future reference. Maxim has advocated for a slightly different approach, used for example at the NEERC: work through the analysis in advance, preparing a presentation with one or two slides per problem listing the key points  then talk through them during the actual analysis. The blackboard analysis tends to be more connected with the audience, since they feel as if they’re creating the solution together with the presenter, and thus are more likely to suggest fixes and improvements; it also requires comparatively little preparation from the presenter.  At the same time, the presentation helps a lot in case the presenter’s or the contestant’s English is not very good so verbal communication is much less effective, and it also leaves a much more convenient reference to use later compared to the video recording; the greater advance preparation makes it easier to avoid incorrect solutions and to present different approaches. Which way do you prefer? Vote at my Google+.

Thanks for reading, and see you next week!

Thursday, April 16, 2015

This week in competitive programming

This week contained two TopCoder rounds. The first one was TopCoder SRM 655 on Thursday (problems, results, top 5 on the left). Gennady 'tourist' showed really outstanding performance getting the highest score on all 3 problems, and the highest gain on challenges (+350) to boot - awesome job!

Here's one of the problems Gennady was the fastest to solve - in fact, he spent just 2 minutes and 44 seconds on reading the problem statement and implementing the correct solution. You're given a 20x20 square board initially painted white, and can repeatedly pick a kxk square on it and paint it either black or white, possible over previous painting. Is it possible to obtain the given picture this way?

TopCoder Open 2015 Round 1A followed on Saturday (problems, results, top 5 on the left). Top 250 active contestants were given a bye for this round, but still the competition was tough and Sevenkplus came out on top - congratulations!

The 24-hour Deadline24 contest has also happened this week in Czeladź (results, top 5 on the left). The amazing team of Psyho, marek.cygan and Mojito1 has won - congratulations! Check out Psyho's writeup on one of the problems - it's a very interesting read.

And finally, here's some auto-awesomed spring Zürichsee. See you next week!