Ok, more serious now: if we don't use the above theorem, what is expected solution? I can only think of brute force 1 spanning tree & check if another exist, but the complexity in worst case is N(N - 2) * N² = N^N which seems too big..

Nash-Williams-Tutte's theorem, afaik. Here is some paper.

Yeah, for me the algorithm of solving this problem was

1. Try to come up with smth by myself.
2. Type "two spanning trees" in Google.
3. Go to the first link and read the solution there.

Я хранил для каждой вершины set<pair<int, int>> — множество длин путей, заканчивающихся в ней. Потом n - 1 раз проходил по всем ребрам, и для каждого добавлял в v все пути из u с дописанным ребром (u, v) — как-то так:

for (u, v: edges) {
    for (auto p: lengths[u]) {
        a = weight1[u][v] - '0';
        b = weight2[u][v] - '0';
        lengths[v].insert(p.first + a, p.second + b);
    }
}

Больше, чем n - 1 раз, делать это не нужно, т.к. на каждой итерации длина пути растет на 1, а несамопересекающегося пути из N ребер не бывает. Остается только выбрать оптимальный из путей в lengths[1]. Если пути нет, то множество будет пусто — выводим -1.

Всего различных весов путей из не более чем 20 ребер бывает не больше 9*20 = 180, итого в вершине хранится не больше 180^2 = 3.2*10^4 пар. Всего действий порядка N * N^2 * (9N)^2, да еще на логарифм, что вообще-то многовато (~3.8*10^9 при N = 20), но оценка на количество путей весьма и весьма верхняя, так что все заходит. Точнее, наоборот: я сделал вывод, что это завышенная оценка, потому что зашло :)

cgy4ever

https://community.topcoder.com/tc?module=ProblemArchive

You can get this page by click 'Problem Archive' in Dashboard (the default page after you login).

Thanks for the info. That explains why matthew99 can solve it so quickly. :)

And it seems I need to read all tasks in that OJ.

"Simple dfs" is essentially a greedy solution. You visit each vertex at most once and if you were not lucky enough to find the correct path at the first try you won't ever consider other paths to a vertex. A small counterexample is

..91
..11
91.1
111.

As is often the case, dynamic programming works in this problem while greedy does not. Try to find a state of the form (last_visited_vertex, something_else).

UPD. I've read your solution one more time. What you wrote is in fact a backtracking solution that has a misleading name 'dfs'. Your mistake is probably that in some cases you forget to set back vis[u] to false in the loop. Such exhaustive search should not work for this problem because of its high time complexity but the top-scoring solution suggests that it could work if you add some pruning.

http://apps.topcoder.com/wiki/display/tc/SRM+685

Dynamic Programming or Memoization with BitMasks.( E * (2 ^ N) * (5 ^ 3) )

State is (msk,r,g,b). Your return value is a boolean.

The mask represents nodes with degree bigger than zero.

Suppose we have an edge connecting nodes u and v.

An edge can only be added if at least one of deg(u) or deg(v) is zero to maintain growing a spanning tree. (

We can only have up to (n-1) / 3 edges of each colour given the constraints, both r ,g and b cannot exceed 5. ( otherwise we just prune this impossible state. 2^13 * 13 * 13 * 13 will give MLE ( Java ) ).

In our DP:

Iterate over all edges, if it’s possible to add this edge, set both nodes it connects to 1 in the bitmask, increase r,g or b depending on the edge’s colour.

After each step recurse further.

Base case: When mask contains n 1’s it means we have used (n-1) edges which means our tree ready. Check if every colour in our state equals k / 3.

Another solution for the problem could be something like this :

Let us fix a root for the final spanning tree and to every other vertex assign a color (among the R/G/B). Since the root is fixed, we can associate each vertex with an edge (connecting the vertex with its parent) and assigning color to the vertex can be thought of as assigning color to the corresponding edge. Given such a configuration (a fixed root and a color for each node) we can check using simple bfs whether such a spanning tree is possible or not by starting at the fixed root and exploring only those edges which have the same color as the vertex explored by those edges.

We can check all possible configurations which turns out to be O(n*3^(n-1)*|E|) which looks pretty large but since we need to check only those cases where number of edges of each color is same, a lot of the search space is pruned and it works well in time. You can have a look at this accepted solution for more details :

http://pastebin.com/nhiNXWFq

Can anybody tell the idea of the problem?

Does it has something to do with eigen values of the Laplacian matrix?

I haven't implemented it but I guess we can do the following:

Let g be the primitive root of 10⁹ + 7.

For each x = g⁰, g¹, ..., g²⁹⁹⁹⁹ and x = g⁰, g³⁰⁰⁰⁰, ..., g^999990000 generate a tree with up to 150 vertices and x MSTs. (I'm not completely sure but we can find these trees like the original problem)

Connect them with an edge.