A prime week

The second week of 2016 was very calm, with the main anchor being the SnarkNews New Year Prime Contest (problems requiring Yandex login, results, top 5 on the left), containing the problems that were previously given in 2015 but were not solved by anybody then. XZ Team and Swistakk showed amazing skill in solving 11 and 8 problems respectively - remember, nobody could solve any one of those problems in actual contests!

Here's a problem from this contest that I could solve. You are given a positive integer A with at most 1000 digits. Find any two positive integers X and Y such that X+Y=A, and both X and Y are palindromes when written in decimal notation without leading zeroes.

Finally, let's remember the problem I highlighted in the previous post: you're given a list of all edges in a tree with n vertices, n is at most 200000. Each edge is given by the numbers of its vertices, but the numbers are not given directly - instead, you just now the number of digits in each number. For example, the edge "123 45" would be given as "??? ??". Your goal is to replace the question marks by digits, such that each number has no leading zeros, and the edges form a valid tree.

We have at most 6 types of vertices in this problem: from "?" to "??????". Since we know the number n, we know how many vertices of each type we have. Let's construct the tree a-la the Prim algorithm: start with a single vertex, let's say the one with label "?", and then add edges one by one, each edge connecting a vertex already in the tree with a new vertex. When we add an edge "??? ??", for example, we either connect an existing "??" vertex with a new "???" vertex, or an existing "???" vertex with a new "??" vertex, so we either increase the number of existing "??" vertices by 1, or increase the number of existing "???" vertices by 1. And our goal is to achieve the predetermined number of vertices of each type in the end.

This looks to be a standard flow problem now: our network will have a source, a sink, a vertex for each edge type in the input (i.e. "?? ???" and "??? ??" are the same type), and a vertex for each vertex type (i.e. "??") in the resulting graph. We add an arc from the source to each edge type with capacity equal to the number of edges of this type in the input, two infinite capacity arcs from each edge type to the corresponding vertex types, and an arc from each vertex type to the sink with capacity equal to the number of vertices of this type in the result, minus one for "?" type. A unit of flow from "?? ???" to "??" will tell us that this edge should connect an existing vertex of type "???" to a new vertex of type "??".

However, this solution doesn't yet work as written. As we start to construct the actual tree from the flow, we might find that we want to connect an existing vertex of type "???" to something, but there's no existing vertex of type "???" yet! And there might not even be an ordering of edges that avoids this situation. In order to overcome this difficulty, let's split all edges of the tree into two types: an edge that adds the first vertex of some type, and all other edges. It's not hard to see that we can change the order of adding the edges in such a way that the edges of the first type are added before all others, and that for all other edges we can use the flow solution above since now we have at least one vertex of each type. So the only remaining idea is to just iterate over all possible sequences of the edges of the first type - since there at most 5 such edges, there are very few possibilities to try.

Thanks for reading, and check back soon for the Jan 11 - Jan 17 week!

A multiple language week

The New Year week contained a few topical contests, the first of which was Good Bye 2015 at Codeforces (problems, results, top 5 on the left). Congratulations to Gennady on wrapping up 2015 with another victory, to go with all other amazing victories he has achieved last year!

The hardest problem H required quite a bit of creativity to solve, but had a very simple problem statement: you're given a list of all edges in a tree with n vertices, n is at most 200000. Each edge is given by the numbers of its vertices, but the numbers are not given directly - instead, you just now the number of digits in each number. For example, the edge "123 45" would be given as "??? ??". Your goal is to replace the question marks by digits, such that each number has no leading zeros, and the edges form a valid tree. How would you approach this one?

SnarkNews New Year Blitz contest was another traditional contest for this week (results, top 5 on the left), with specific New Year-themed rules: it runs from a few hours before the New Year to a few hours after it, and the penalty time for each problem is counted as the distance from the New Year - so if you solve a problem before the New Year, it might make sense to wait before submitting it. Of course, submitting exactly at New Year usually clashes with the New Year celebrations themselves, so this contest usually attracts the most devoted participants :) This year an additional rule has complicated the matters: one could earn a -100 penalty minute bonus by submitting a solution in a different programming language.

Congratulations to ariacas on solving all 12 problems and submitting most of them right at New Year, and to Xellos and Alexander Udalov on successfully using 10 different languages each - an amazing accomplishment!

I'm sorry for the interruption in my posts, caused by some pretty busy weeks at work and amazing winter weekends - winter is my favorite season, and I've been doing some cross-country skiing instead of updating this blog. I hope to get back to the current week soon, so please come back for updates!