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!

Tweet