Hi everybody! It was my first experience of writing problems for TopCoder SRM, hope you liked it. I was a writer of Easy and Medium task in both divisions, subscriber was an author of both Hard tasks. In div1 they were harder than usual, but I hope you still liked them.

Div2 easy

This task was just about implementing exactly what is described in the statement. Looks like Python has a built-in support of set comparison. Usually coders using Python have a disadvantage, but in this task it looks more like an advantage :) There are built-in functions for sets in C++ and Java too, I recommend to learn about them even if you successfully submitted this problem.

Div2 medium

Knowing strings a and b, we can build a reverse mapping q[d] = c, that maps the encoded letter d to it's original corresponding letter c. For letters that do not appear in b, we remember that we don't know their pre-image. After that, we just apply our mapping q to a string y. If some of letters doesn't have a pre-image, we should return "", otherwise we return q(y).

There is an only special case that appears in sample tests: if we know pre-images of all letters except one, we may still uniquely understand what is its pre-image: it is the only letter that doesn't appear in string a.

Div2 hard

This task is an easier version of Div1-hard. In this version it was enough to write a BFS on a graph of all possible states. In this task the state is a set of all already people. Each set can be represented as a binary masks no larger than 2¹⁸ = 262144 that is small enough to fit in TL.

Div1 easy

A first solution coming to a head works in : all we need is to just simulate the process. Suppose we are now standing in number n, the last hour was h, it means that we need to find a first divisor of n or n - 1 larger than f and perform n +  +  or n –  depending on whose (n or n - 1) divisor appears first. Although, one can build a test where number of steps is ~2000, it makes this solution pretty hard to fit in time limit, one of such tests is a last sample test.

The key observation is that when we change our number, we don't need to find divisors of a new number from scratch. The well-known divisor finding algorithm consists of two stages: first we consider all divisors smaller than , then all divisors larger than . If we were on the first stage, then we just need to continue iteration from the same place for a new number. If we are on the second stage, we also continue iterating the second stage with a new number. This works in since our number can't infinitely increase (it can be shown that it can't move further than 2n, actually it doesn't move further than 100).

The other solution was to cache the divisors for all values of n that happen during the execution.

Div1 medium

The first observation is that an almost-Eulerian graph can be obtained from a unique Eulerian graph. Indeed, if we have an almost-Eulerian graph G that is not Eulerian, then there exists the only pair of vertices u and v that have an odd degree, the only possible original Eulerian graph G' is (here means inverting the specific edge, adding it or removing it). If G is Eulerian itself, then we obviously can't invert some edge keeping it being Eulerian.

This means that if there are E_n Eulerian graphs, then there are exactly almost-Eulerian graphs: each Eulerian graph G produces itself and all possible as almost-Eulerian graphs.

Now we need to calculate number of Eulerian graphs on n vertices, E_n. It's well-known that the graph is Eulerian iff it is connected and all its vertices have even degree. The good idea is to first calculate D_n, the number of graphs with all even degrees. If we succeed in it, we can then calculate E_n by using inclusion-exclusion principle on D_n.

How many even graphs on n vertices are there? The simplest way to understand that is to remove some vertex from it (let's say, a vertex 1) and notice that the graph on remaining vertices 2, ..., n may contain an arbitrary set of edges. Indeed, if there are some odd vertices among them, then when we return vertex 1 back to the graph, we have to connect it to all odd vertices among 2, ..., n. After that all 2, ..., n become even vertices, and 1 itself also becomes even due to handshake lemma. So, the answer is since there may be any possible set of edges between vertices 2, ..., n and all edges from 1 to the rest of the graph may be uniquely determined.

Now how to calculate E_n. We know that E_n = D_n - R_n where R_n is number of disconnected even graphs. Suppose that the connected component that contains vertex number 1 consists of k vertices (obviously, 1 ≤ k ≤ n - 1). Then there are ways to choose k - 1 vertices in this connected component from n - 1 remaining vertices, also there are E_k ways to organize a connected component that has all even degrees and there are D_n - k ways to organize an even graph on the rest of the vertices (note that it may possibly be disconnected if there were 3 or more components in the original graph, that's why we use D_n - k but not E_n - k here). So, there is a recursive formula: that leads us to an O(n²) DP solution.

Div1 hard

I'll describe an approach for this problem very briefly.

What we actually need in this task is to understand how the described process works. We can describe the process in following way. The detective acts almost like a Prim's algorithm: in each step he adds one of the maximal edges between the already visited set and the rest of the vertices in the graph. The only thing that we may adjust is an order of choosing the edges with the equal cost.

At any moment the visited vertices form some part of a maximum spanning tree. Suppose we want to get to vertex x in minimum number of steps. Consider the resulting path between 0 and x. It is a well-known fact that the minimum edge on this number is uniquely defined and is equal to a maximum possible minimum edge among all paths from 0 to x. Suppose the value of this edge is equal to d. We can calculate d by running a Floyd algorithm modification for metric d(u, v) =  minimum on path between u and v, that is needed to be maximized.

There are edges of two kinds on a path from 0 to x: those who are equal to d and those who are larger than d. In any situation we prefer larger edges, so when we touch a vertex with some outgoing edges larger than d, we will greedily first visit all those edges. So, let's contract all components connected by edges larger than d.

After contracting all we need is to find a shortest path from 0 to x remembering that each time we visit a vertex, we have to add a size of its connected component described above.