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 10⁵ times, each time is at most 10¹⁸), 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!

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 (problems, results, 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!

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!

This week in competitive programming

ZeptoLab Code Rush 2015 was the only contest this week (problems, results, top 5 on the left). Gennady got a clear first place with another flawless performance - congratulations!

One of the easy problems, problem C, was a good example of the argument that leads to square roots in asymptotic complexity of various algorithms. The problem statement was very simple: you are given two types of candy, one costs X per item and each item brings P units of joy, and the other costs Y per item and each item brings Q units of joy. What's the maximum amount of joy you can get after spending at most Z? Of course, you can't buy partial items, as otherwise we can simply buy the candy with the best joy/cost ratio. Can you solve this problem in O(sqrt(Z))? How about O(poly(log(Z)))?

One of the problems I've described last week was about counting strings of given length with the given value of a polynomial hash. The way to solve it was to notice that after we know the hash of the first n/2 characters, let's say it's equal to X, and the hash of the last n/2 characters, let's say it's equal to Y, then the hash of the entire string is simply X*p^n/2+Y. In other words, in order to find the number of ways to reach the given hash value, we need to sum the products of numbers of ways to reach two hash values for the halves that sum to the given value - now we can notice that this is equivalent to multiplying polynomials. Polynomials can be multiplied in O(NlogN) using Fast Fourier Transform. Moreover, very conveniently (but not suprisingly), one needed to output the answer modulo a prime 998244353=2²³*119+1, which means that there exists a 2²³-th root of unity modulo that prime, and thus the FFT algorithm can work just fine.

Here's an interesting addition: this comment (in Russian) describes a way to multiply two polynomials modulo some number that does not have a nice root of unity, so this problem would actually be solvable just fine modulo 10⁹+7 or any other modulo of that order of magnitude.

Thanks for reading, and check back next week!