A week with randomized travel

Quite unusually, this week had two Codeforces rounds. The first one, Codeforces Round 309, took place on Wednesday (problems, results, top 5 on the left). Congratulations to ecnerwal for his second Codeforces victory! The scoreboard is a bit unusual, too, as all successful submissions for the top 5 happened within the first hour, highlighting the huge gap in difficulty between problem E and the rest. I haven't solved it myself yet, but the problem statement looks interesting: you're given a graph with 50 vertices and 100 edges, where each edge has a cost and a travel time associated with it, and the travel time is actually a random value: you're given the probabilities that it's equal to 1, 2, .., t (t <= 20000). You need to get from vertex A to vertex B, and if you spend more than t time doing that, you pay an additional constant penalty. How do you minimize the expected payment for getting from A to B?

Codeforces Round 310 happened on Saturday (problems, results, top 5 on the left). The problems were more tractable this time, and the order of solving them played the key role - congratulations to Borys on getting that right and claiming the first place!

Challenge24 finals in Budapest covered both Saturday and Sunday (results, top 5 on the left). There is little information available right now, but the final scoreboard is, and team HoChockiGon is the winner, overtaking the last year's champions PrecisionScrewdrivers in Sunday's morning hours - nice push!

Last week I mentioned the nice problem H2 from the IPSC: you're given an undirected graph, and need to color its vertices into red and blue in such a way that the total number of edges between the red vertices is as close as possible to the total number of edges between the blue vertices.

The key idea is: it turns out that the problem is equivalent to finding a subset of vertices with total degree as close to half of the total degree of all vertices as possible! Having made this observation, the rest is very straightforward dynamic programming.

Thanks for reading, and check back next week!

A week with H2

IPSC 2015 was the main event of the week (problems, results, top 5 on the left, analysis). The scoreboard looks suprisingly similar to last year: R+T+J on the top with 35 points (great job!), then HoChockiGon. The Polish team is now closer to the first place, with a 3 point gap instead of 6 points a year ago.

Among the problems my team didn't solve, I'm particularly disappointed not to solve problem H2 which was a very nice "classical" problem: you're given an undirected graph, and need to color its vertices into red and blue in such a way that the total number of edges between the red vertices is as close as possible to the total number of edges between the blue vertices. The solution is very simple and elegant, and after seeing it you don't understand how you could've missed it in the first place :)

TopCoder Open 2015 Round 2B was the other contest this week, with another 40 advancing to the final online selection stage (problems, results, top 5 on the left, parallel round results). One could compete onsite in San Francisco or online, and most fittingly the top 5 are all based in California (how many were actually onsite?). Congratulations to ACRush on continuing the 100% record in TopCoder in 2015, both in algorithm and in marathon!

Finally, let me come back to a problem I mentioned last week: you are given a row of n devices, each consuming some subset of k<=8 different resources when turned on, and producing some amount of energy when turned on. For each l from 1 to n you need to find the smallest r such that it's possible to turn on some devices from the segment [l;r] such that no two devices turned on consume the same resource, and that the total energy of the devices turned on is at least z.

When the left boundary l is fixed, we can use the following dynamic programming: start moving the right boundary r to the right, and maintain the highest possible energy we can obtain from each possible subset of resources in a 2^k-element array, spending O(2^k) operations on updating the dynamic programming array with a new device, As soon as the highest possible energy for the "all resources" exceeds z, we're done.

Now suppose we've ran this algorithm for some l, and now need to switch to l+1. First, it's easy to see that r will not decrease, so we should be able to just continue our dynamic programming from where we left off, and thus process all data in O(n*2^k) time. But we've missed an important step: we also need to somehow "remove" the l-th device from our dynamic programming array, and it's not clear how to do that.

However, if we had to remove the r-th device from the dynamic programming array instead of l-th device, it would be easy: we can just remember the state of the dynamic programming array before we added r-th device, and revert to that. In other words, we know how to work with a stack, but need to work with a queue. And of course, the computer science has the answer: one can emulate a queue using two stacks! Ever wondered if this textbook construction is practical? Well, now you know.

Having two stacks instead of one queue makes checking if we can produce at least z units of power slightly more difficult, but it still takes only O(2^k) operations since we need to iterate over all ways to split the set with k elements into two, and the total running time of this solution is thus O(n*2^k).

Thanks for reading, and check back next week for the Challenge24 results (a picture from last year from the official website is on the left)!

A 25+25+50+10 week

TopCoder SRM 661 took place very early on Friday after a mostly calm week (problems, results, top 5 on the left, discussion). One of the highlights of the round is the screencast by subscriber where he has also thought aloud and recorded his voice - check it out if you understand Russian! When solving a problem, it's always helpful to discuss it with somebody, and in many cases simply explaining yourself in words helps understand the solution better and improve it - so it might be that intentionally telling the thoughts loudly actually leads to better results! Definitely need to try this out myself.

Yandex.Algorithm 2015 Round 2.2 gave contestants the final chance to get into the top 25 in overall selection results (problems, results, top 5 on the left, overall selection results, discussion). Unlike the previous round, where the best result with at least two blind submissions was 20th place, this one was not so brutal and Jacob Dlougach has appropriately used the time bonus to claim fourth place. Still, places 1-3 and 5-16 have at most one blind submission each, suggesting that this problemset, authored by GlebsHP, also had a lot of tricks. I wonder if the problemsetter for the final round will be revealed in advance - it seems that this can significantly affect the strategy choices.

Google Code Jam 2015 Round 3 has chosen another top 25, this time to fly to Seattle (problems, results, top 5 on the left, discussion). The intersection between this top 25 and the Yandex one is just 7 people: tourist, iwi, vepifanov, dzhulgakov, AngryBacon, ishraq and qwerty787788 - hope I didn't forget anybody - the intersection is small probably due to the difference in competition formats, the task types, and just to the natural randomness.

The problems presented quite different types of challenges, but here's a particularly nice one. You are standing on a line in point 0 and can run at speed v, and there are n quail running away from you, i-th quail at point p_i (can be positive or negative) running away at speed v_i. What's the smallest time required to catch all quail? n is up to 500.

The two approaches that come to mind for such problems are greedy algorithms and dynamic programming. But it's not clear where would the greedy optimality property come from, and the number of possible states for DP seems exponential - we need to remember which quail we've already caught. Can you see which one of those ideas actually works?

Russian Code Cup 2015 Elimination Round was a bit more generous and chose the top 50 using the 3-hour ACM format (problems in Russian, results, top 5 on the left, discussion in Russian). rng_58 quite succesfully continued working towards his goal of learning Russian by claiming third place in a contest with Russian problem statements only, although most probably translation software has played a part.

The hardest problem was probably the most beautiful, too. You are given a row of n devices, each consuming some subset of 8 different resources when turned on, and producing some amount of energy when turned on. For each l from 1 to n you need to find the smallest r such that it's possible to turn on some devices from the segment [l;r] such that no two devices turned on consume the same resource, and that the total energy of the devices turned on it at least z. Solving this problem for each particular value of l is a relatively straightforward dynamic programming question, but given that n is up to 100000, we can't affort to solve each l separately.

And finally, Google Distributed Code Jam 2015 Online Round brought an entirely new competition format to the best competitors in the world (problems, results, top 5 on the left, discussion). Of course, it might turn out that the best competitors for this new format will be completely different ones - that's why it's so exciting to see how it pans out.

So far, it looks like the competition went well, and there are only two competitors who have qualified both for the regular and for distributed Code Jam: simonlindholm and bmerry, definitely suggesting that the distributed part tests quite different skills. People who participated: do you share this feeling? Was solving these problems similar to more usual contests?

Thanks for reading, and see you next week!

A week where OEIS helps understand the problem

Another eventful week in competitive programming comes to a close. First up was TopCoder SRM 660 (problems, results, top 5 on the left). After wasting about 25 minutes and getting a very low score on the 250, I've decided to go for 1000 in a bid to still win the match. This turned out to be a good strategy, if only I could finish the solution in time - but I ended up requiring 4 more minutes to get it to work after the end of the coding phase (it passed system tests in the practice room). In the absence of any solutions for the 1000, sky58 has won the SRM thanks to his fastest solution for the 500 - congratulations!

Solving the 1000 could be split into two big parts: coming up with easy-to-understand combinatorial objects that we needed to count, and counting them. The second part was a tough but relatively standard exercise, so I want to cover the first part now.

The problem statement was: consider sequences of N integers, each between 1 and N, inclusive, such that each integer appears at most K times. Consider the following operation on a sequence: pick two arbitrary numbers X and Y from 1 to N, replace all occurrences of X in the sequence with Y and vice versa, and then swap X-th and Y-th elements of the sequence. Consider two sequences equivalent if they can be transformed into each other using several such operations. How many different (pairwise non-equivalent) sequences exist?

This looks to be a quite abstract, and to be honest, arbitrary class of sequences and operation to work with, so it's hard to come up with a way to count equivalence classes. However, it turns out that these sequences are just a different description for a very natural combinatorial object! Can you see which one?

Here's how I approached this. I've quickly wrote an exhaustive search solution that solved this problem for small values of N and K. I've then written down the answers for small values of N and K=N (effectively no limit): 1, 3, 7, 19, 47, 130. I've entered those numbers into the OEIS - and the only result says that this is the number of different mappings from a set to itself (up to renumbering of elements in the set). Having seen that, it's clear where does the operation from the problem statement come from - it's simply switching the numbers of two elements in the set!

Now we just need to count the number of different mappings such that at most K elements map into any single one. This is not an easy task, but it's quite standard and I won't go into detail.

Yandex.Algorithm 2015 Round 3 took place on Saturday (problems requiring login, results, top 5 on the left). Some usual suspects like tourist, Egor and dzhulgakov shared the top 5 with the rising stars umnik2296 and ishraq.huda. Congratulations to all for amazing results!

Codeforces got a part of the competition pie with Looksery Cup 2015 (problems, results, top 5 on the left). Problem H had a very simple statement, and yet allowed a multitude of different solutions, some much easier to implement quickly and avoid bugs in than others. You are given a 2x2 matrix, and you are allowed to add arbitrary 2x2 matrix with zero determinant to it. You need to minimize the maximum absolute value in the resulting sum. How small can you make it?

Gennady has submitted it just 6 minutes into the contest, and it was his second problem to submit :) His first place in this contest never seemed in doubt until two contestants have managed to pass pretests on the hardest problem E - but they both failed the final testing, and Gennady has returned to the top spot. Congratulations on the impressive performance!

Thanks for reading, and check back next week as we start to approach the decisive phase of many tournaments: Google Code Jam and Russian Code Cup will both hold their final elimination rounds, with 25 best competitors selected to fly to Seattle for Code Jam finals, and 50 best competitors chosen to compete for the RCC in the online finals. What's more, the Distributed Code Jam will give the same contestants a chance to try their skills in a completely different - some might say more contemporary - environment: when you have quite a lot of machines to throw at a problem. I'm excited to see how this competition works out - good luck to all participants!

A week with a new max-flow problem

Codeforces Round 305 started this week's competitions on Tuesday (problems, results, top 5 on the left). Nobody got all problems right despite the promise of an easy contest, and dreamoon got the first place being the only one to solve the two hardest problems correctly - congratulations!

Google Code Jam 2015 Round 2 took place on Saturday at the time which minimizes the number of people who have to compete in the middle of the night - 14:00 UTC (problems, results, top 5 on the left). Gennady has earned another very convincing victory - amazing performance!

The three harder problems gave everybody a chance to shine in the area one likes the most: a tricky greedy requiring careful implementation, a nice max-flow graph puzzle, and a logical case study together with Burnside's lemma or combinatorial dynamic programming. Solving any of these three problems together with the easy problem A was enough to advance to the next round.

The max-flow (spoiler alert :)) puzzle was, in my opinion, the most beautiful. You were given at most 200 sentences containing at most 3000 words in total, and told that the first sentence is in English, the second is in French, and the rest is unknown. You needed to pick a language for each sentence in such a way that the number of words that appear in both languages is minimized. Can you see how to do it? The problem statement is so simple that makes me wonder if somebody has already come up with something similar - have you encountered something like this before?

Russian Code Cup 2015 Qualification Round 3 was the last chance to advance to the next stage for Russian-reading contestants (problems in Russian, results, top 5 on the left). The two top spots with just one minute of penalty time difference were occupied by GlebsHP, the double ICPC gold medalist, and KAN who needs to live up to quite big expectations at the next year's ICPC. Congratulations to Gleb and Nikolay!

TopCoder Open 2015 Round 2A has wrapped up the week (problems, results, top 5 on the left). This time it was KAN's teammate's turn to convincingly claim the top spot - way to go Vlad!

8 out of the 42 competitors who advanced to the next round were competing onsite in St Petersburg ITMO, including three out of the top five. It was exciting to meet with everybody again - thanks a lot to TopCoder and ITMO for organizing the event!

The medium problem required making several simplifying steps in sequence, and thus is a good example to train on. You are given a tree where each edge has an integer length, and some nodes of the tree contain foxes. What is the smallest number D such that it's possible for each fox to travel at most D, ending up in a vertex, in such a way that the vertices occupied by foxes form a connected subset?

The first step is straightforward: when you are asked "what is the smallest number D such that", it's often wise to learn to answer "is the given number D enough" question and apply binary search to solve the original problem. But what would you do next?

Thanks for reading, and check back next week!