Friday, August 5, 2016

Google Code Jam 2016 finals live stream

The final round of Google Code Jam 2016 has just started, and you can follow along the live stream. Enjoy!

Monday, August 1, 2016

A Young week

Lacking the usual Codeforces and TopCoder rounds, this week has nevertheless provided some great problems to solve. On Friday, Yandex.Algorithm 2016 Final Round pitted the best 25 in the world against each other for the fame and roughly $5000 first prize (problems with Yandex login, results, top 5 on the left, online mirror results, analysis, my screencast). Egor has won with a sizeable margin mostly thanks to quick and correct solutions to the very tricky problems B and F - great job!

Nobody has managed to solve problem E during the round, which is a pity since the solution is quite beautiful. Here's what the problem asked: consider sequences of 2n parentheses of n different types such that there's exactly one opening and exactly one closing parenthesis of each type. A sequence is considered good if the parentheses can be colored with two colors in such a way that the subsequences formed by each color are balanced parenthesis sequences. How many good sequences exist for the given n? n is up to 500.

A Japanese competition website AtCoder has recently started supporting English, and ran AtCoder Grand Contest 002 on Sunday (problems, results, top 5 on the left, analysis, my screencast). The Code Jam-like penalty system allows one to solve the problems in arbitrary order, and semiexp took full advantage of that by starting with the fourth problem, and still being the fastest to finish. Congratulations!

Problem E was a nice game analysis task. Two players were playing on a Young diagram by placing a token in the top left corner, and then taking turns in moving it. At each move, a player can move the token either down or to the right. The player who can't make a move loses. Who's going to win if both play optimally? There are at most 105 rows, each at most 109 in length.

I've mentioned quite a few problems last week, one of which was: you are given an undirected graph with at most 1000 vertices and at most 1000 edges, such that each vertex has at most three adjacent edges. Each vertex also has a weight, and you need to pick at most K edges maximizing the total weight of vertices covered by (adjacent to at least one of) the picked edges. The interesting aspect is that K is really small: at most 7. So you're allowed algorithms exponential in K, but polynomial in the size of the graph.

The key to solving this problem is the following observation. Consider the edge e that has the highest sum of weights of its ends. Taking e unconditionally into the answer would be greedy which does not always work. But let's think a bit more why it might not work. Consider the case where the optimal answer does not contain e. If that answer also does not contain any other edges incident to the ends of e, then we can add e to that answer, remove any other edge, and obtain another answer with the same or greater score, as e has the highest sum of weights. That means the optimal answer should contain either e, or one of the edges adjacent to its ends. And since the degree of each vertex is at most 3, that means we have at most 5 edges to choose from!

Having made this observation, we can complete the solution in several possible ways. The most straightforward way is to put all edges into a heap using the total weight of uncovered edges as the key, allowing us to find the maximum edge quickly, and thus completing our search roughly in 57 operations. Another way is to take the same argument slightly further by noticing that all edges of the answer must be among the 5*7=35 edges with the highest total weight of the ends, as otherwise there will be at least one edge there that does not have common endpoints with any edge of the answer, and thus replacing the cheapest edge with it would improve the answer.

Thanks for reading, and check back next week!

Sunday, July 24, 2016

A fixed-parameter-tractable week

This week had quite a few competitions, culminating in the ultimate TCO elimination round where one had to place in top 4. But before we come to that, let's start with TopCoder SRM 695 on Tuesday (problems, results, top 5 on the left, my screencast).

The medium problem was from a relatively new but growing family of problems inspired by the theoretical concept of fixed-parameter tractability: you are given an undirected graph with at most 1000 vertices and at most 1000 edges, such that each vertex has at most three adjacent edges. Each vertex also has a weight, and you need to pick at most K edges maximizing the total weight of vertices covered by (adjacent to at least one of) the picked edges. The interesting aspect is that K is really small: at most 7. So you're allowed algorithms exponential in K, but polynomial in the size of the graph. Can you come up with one?

After a 30-minute break, Codeforces Round 363 followed (problems, results, top 5 on the left, my screencast, analysis). Some of the problems in this round were from the VK Cup onsite finals, but I've not yet seen the mapping between this round's problems and the onsite final round problems. Does anybody have it?

The hardest problem in this round was an great example of slowly and gradually (one might even say tediously :)) unwinding a problem, combining ideas from combinatorics and arithmetic - as opposed to problems that require just one, if brilliant, idea to be solved. The problem statement was relatively simple: we define a permutation of integers between 1 and n to be coprime, when a pair of its elements is coprime if and only if their 1-based indices are coprime. Given a partially filled permutation (some numbers known, some arbitrary), how many ways are there to complete it as a coprime permutation?

Codeforces Round 364 on Friday was also based on VK Cup onsite finals problems (problems, results, top 5 on the left). Ainta has solved the very difficult problem D in just under 40 minutes, and was able to cruise to an easy victory afterwards. Congratulations!

I'm still curious how to solve even more difficult problem E, as string problems were always my weak spot and I'd love to learn more about them. You are given a string with 200000 characters. You need to form the longest possible sequence of strings starting with the given string, and such that each following string appears as a substring at least twice in the preceding string (those two occurrences may partially overlap).

And finally, we come to TopCoder Open 2016 Round 3A, where only top 4 participants would earn a spot in the onsite competition (problems, results, top 5 on the left, my screencast). In the aftermath of this round, an interesting discussion about appropriate problems for high-level tournament round ensued. What's your view?

I've enjoyed all three problems in this round, but the 250 seems to be the most well-received by everybody. You are given a permutation of integers between 0 and 2n-1. You need to come up with any balanced parenthesis sequence that stays balanced when we apply the given permutation to it (i.e., if the 5-th element of the permutation is 9, then the parenthesis on position 5 of the first sequence moves to position 9 in the second sequence). n is up to 25.

Thanks for reading, and check back next week!

A lull week

Last week was the lull before the storm, with just one contest among the usual suspects: Codeforces Round 362 (problems, results, top 5 on the left, analysis). TooDifficuIt has won and confirmed his third place in the overall rating list - in fact, he's now much closer to the top two than the fourth place is to him. Congratulations!

Thanks for reading this super short summary, and check back soon for this week's contests which are aplenty.

Monday, July 11, 2016

A testcase preparation week

CodeChef SnackDown 2016 Final Round in Mumbai has continued the run of two-person team contests this week (problems, results, top 5 on the left). The winning team was 50% the same as last week - congratulations Gennady and Boris!

TopCoder SRM 694 followed a few hours later (problems, results, top 5 on the left, my screencast). The problems were quite standard, and jcvb and xudyh showed great mastery of flow algorithms to solve the 900 very fast and keep the battle for the first place just between themselves. In the end jcvb emerged victorious by a mere 0.09 points - congratulations!

Unusually for TopCoder there was quite some time to spare at the end of the coding phase, and thus one had the opportunity to prepare for the challenge phase thoroughly. The required mindset is quite similar to the one of the problemsetter: need to come up with testcases that would fail various potential incorrect solutions, and ideally with ones that are likely to fail even unforeseen incorrect solutions, too.

Here's the approach I've chosen this time for the easy problem (you can see it in more detail, but a bit slowly, on the screencast): let's construct random testcases that have many parts, and yet exactly one way to group the parts to achieve the maximum score. An incorrect solution in this problem is likely to be some kind of greedy instead of dynamic programming, and having exactly one solution makes sure that there are many more ways for the greedy to make mistakes. Having the testcase random instead of manually crafted ensures that it doesn't become too well-structured, as greedy solutions might actually be correct for well-structured cases.

More precisely, I've started with just three numbers which would be the xors of the groups in the final answer, and then repeatedly tried to replace any number x with (x xor y, y), where y is a random number, checked if there's still just one way to achieve the maximum, and if yes, then kept the replacement. I've generated a few cases using this approach, and picked the one with more components, and without components that looked too simple (powers of 2).

When I opened a greedy solution during the challenge phase (screencast pointer), I could then successfully use the testcase prepared in advance without crafting a case specifically against that solution. My other challenge (screencast pointer) was a bit more straightforward :)

How did you prepare for the challenge phase this time? Or maybe you remember a useful challenge phase preparation trick you've used earlier?

Codeforces held the online mirror of the 2016 Helvetic Coding Contest on Sunday (problems, results, top 5 on the left). The onsite version took place quite a while ago, and had slightly different problemset and rules. Congratulations to team Zg on earning the victory with more than an hour to spare, and on coming head and shoulders ahead of all onsite teams as well!

Thanks for reading, and see you next week!

Saturday, July 9, 2016

An under 23 week

The last week was exclusively on Codeforces. First, Codeforces Round 360 on Wednesday provided top competitors ample time both for solving all problems and for challenging the solutions of others (problems, results, top 5 on the left, analysis). The top 3 stood out because of the challenges, but TooDifficult has also executed everything in the right order - solving before spending too much time on challenging - and thus claimed the first place. Congratulations!

VK Cup 2016 Finals was the main event of the weekend (results, top 5 on the left). Unlike last year, the winning team, built from the top two teams of 2015, didn't really leave the others any chance. Congratulations on the super convincing victory, Adam and Gennady!

My previous summary included a nice TopCoder problem: you are given just one integer k between 1 and 109, and need to construct a bipartite graph with exactly k perfect matchings. Not any such graph will do: it must have at most 20 vertices in each part, and at most 120 edges. There can be more than one edge between the same two vertices, and all those edges are distinct for the purpose of counting the number of perfect matchings. Apart from those restrictions, you're free to construct the graph in any way you like.

I think there are two main approaches to this kind of problem. One is to start with a random solution, and then keep modifying it towards the required property. I don't have a good feeling whether it would've worked in this problem, although I won't be surprised if it would. The other is to learn how to build answers for some values of k, and how to combine those together, and then represent the required number as a sum or product of primitives we know how to build.

Those primitives in this problem are somewhat atypical: the values of k=3n. It's quite straightforward to construct a graph with exactly 3n perfect matchings: it will have n vertices in each part, and for each i it will have 3 parallel edges connecting the i-th vertex in the first part with the i-th vertex in the second part. We haven't yet exceeded our limit of 20 vertices in each part, as 320 is more than 109. Every other value of k can be represented in base-3 as a sum of powers of 3 (each taken 0, 1 or 2 times), but how do we achieve addition of the numbers of perfect matchings?

Well, addition in combinatorial problems usually means that there's a choice: variant a leads to x possibilities, variant b leads to y possibilities, so if we have to choose exactly one of a or b we have x+y possibilities. And matchings lend themselves well to having choices: for each vertex, we have to choose which vertex it will match. So if we want to build a graph with 3n+3m perfect matchings, we can make one of its vertices have exactly two adjacent edges, picking one of them would lead to 3possibilities of matching the rest of the graph, and the other would give 3m.

And here comes the "pull an idea out of the blue sky" moment: let's start with a graph with 19 vertices in each part and 3 parallel edges from connecting the i-th vertex in the first part with the i-th vertex in the second part, as before. Now let's add a 20-th vertex to both parts, without adding any edges initially. Then we add one edge from i-th vertex of first part to (i+1)-th vertex of the second part for all i between 1 and 19. The 20-th vertex in the first part still has no adjacent edges: this vertex will be the pivot representing addition. If we want to add 3i perfect matchings for any i between 0 and 19, we'll add an edge from the 20-th vertex in the first part to the (i+1)-th vertex in the second part. Were a perfect matching to include this edge, it's not hard to see that matching of vertices with numbers (i+1) and up is uniquely determined - we have to use the diagonal edges. The matching of vertices with numbers up to i, on the other hand, must use the horizontal edges, with 3 choices for each, and thus we have exactly 3choices in total.

We can represent any sum of powers of 3 between 30 and 319, possibly with repetitions, in this way. The base-3 representation of any k up to 320-1 will require at most 2*20=40 summands, which require 40 edges in our graph. In addition to those, we have 3*19 horizontal edges and 19 diagonal edges, so the total number of edges doesn't exceed 40+4*19=116, which is good enough. Also note that the boundary is quite tight, so other similar constructions might not work.

Thanks for reading, and check back for this week's summary!

Monday, July 4, 2016

A perfectly matching week

The June 20 - June 26 week was much calmer than the previous one. There were two "regular" rounds, the first being Codeforces Round 359 on Thursday (problems, results, top 5 on the left, analysis).

The second regular round was TopCoder SRM 693 on Saturday (problems, results, top 5 on the left, my screencast).

The medium problem was from the rising category of "constructive" problems. You are given just one integer k between 1 and 109, and need to construct a bipartite graph with exactly k perfect matchings. Not any such graph will do: it must have at most 20 vertices in each part, and at most 120 edges. There can be more than one edge between the same two vertices, and all those edges are distinct for the purpose of counting the number of perfect matchings. Apart from those restrictions, you're free to construct the graph in any way you like. Can you solve this one?

Challenge24 in Budapest was the onsite competition of the week, challenging the brave with 24 hours of problem solving (problems, results, top 5 on the left). The scores were extremely close in the final standings, and the winner was team Dandelion - congratulations!

In the last week's summary, I have once again mentioned quite a few interesting problems - let's analyze the IPSC one here. To remind, we're studying two permutations of 2n objects, called L and R. The permutation L is constructed like this: the first n objects in the old order go to odd-numbered positions in the new order without shuffling, and the last n objects in the old order go to even-numbered positions in the new order, without shuffling. The permutation R does almost the same, but the first n objects go to even-numbered positions, and last n go to odd-numbered positions. You are given three numbers: n, a and b. An object is currently on position a in the permutation of 2n objects, and we want to put it to position b using only operations L and R. Construct any shortest sequence of those two operations that achieves it.

Solving this problem involved studying the properties of operations L and R, trying to understand how they work. Such exploration involved several dead ends which I won't describe here, so it might seem that we're progressing almost miraculously :)

First, we will solve this problem from the end towards the start - in other words, let's consider the reverse operations L' and R'. How do they transform our current position x? It's not hard to see that L' moves odd-numbered positions x to x/2 and even-numbered positions x to x/2+n, and R' maps odd positions to x/2+n and even positions to x/2, where "/" stands for integer division (rounding down), and positions are numbered from 0 to 2n-1.

In other words, we repeatedly do the following: remove the last bit of our number, then choose to add or not to add n. Adding n after removing i last bits can also be viewed as adding n*2i in the very beginning. Assuming we do k steps in total, we can add n*2, n*4, ..., n*2k, and that means we can add n*m for any even number m between 0 and 2k+1-2.

After all the additions are done, we remove k last bits, and want to obtain the given number a. It means that before removing the k last bits, our number has to be between a*2k and (a+1)*2k-1.

Which means that the problem has boiled down to: does there exist such even number m between 0 and 2k+1-2 that a*2<= b+n*m <= (a+1)*2k-1?

This is of course easy to check for any given k. Moreover, we can see now that once n<=2k and b/(a+1)<2k there will always be such m, so we need to try only a logarithmic number of k values before we find the answer! Reconstructing the sequence of L and R operations knowing the values of k and m is an exercise in carefully traversing the above reasoning.

I find the way the solution flows from combinatorics to arithmetics in this problem quite beautiful. The solution explained in the official analysis skips the "from the end" part, and thus ends up being even simpler - but then it's not as satisfying to make it work :)

Thanks for reading, and check back soon for this week's summary!