I would like to discuss last SRM problems here since I find much more comfortable CF than TopCoder forums (>.<) and it seems like they stopped publishing editorials here: Where they used to post editorials

I managed to get the first problem accepted, this was a problem with many many hacks, I think because it was kind of easy to go with a greedy approach.

My approach:

Div 1. Level 1

We're given an undirected multigraph with 50 vertices and M edges (1 ≤ M ≤ 20). We need to paint all vertices of the graph, one at a time, and after every time we paint a vertex we have to pay a fee equals the number of edges that have both ends already painted. We want to find the minimum total cost of doing so.

First we note that if we paint second vertex of edge e at time t (starting at t = 0 and increasing t after we paint a vetex) we will have to pay 50 - t in total because of this edge. So if a vertex v is the second vertex to be painted for k_v edges and we paint vertex v at time t_v, we will pay (50 - t_v) * k_v in total for this vertex. Then we see that if we're given the sequence k₀, k₁, ...k₄₉ we would like to paint the vertices in increasing order of k.

To find the solution we iterate over all possible ways of orientating the M edges. For a given orientation of the graph, if edge e = (v, u) is orientated u → v means that v will be painted after u, and vice versa otherwise, also for a vertex v, k_v is simply its in-degree. We calculate the cost induced by the given orientation by sorting the sequence of k's and summing up each k multiplied by 1+its index in the sorted sequence.

Is any orientation a valid one? No, it's easy to see that if an orientation has a cycle, it probably won't induce a valid order for painting the vertices, so we need to check if the orientation is acyclic. Also, the orientation could be acyclic but painting the vertices in increasing order of k won't respect the meaning of the orientation, and the cost calculated won't be the correct one, so we need to check this too, which seems more difficult. But actually we don't have to check anything :) In both cases we can prove that the cost calculated is sub-optimal, so we're happy.

Time complexity O(2^M * Nlog(N)) where N = 50, the number of vertices. (We could sort in O(N) but whatever :))