chrome's blog

Topcoder Single Round Match 685
By chrome, history, 9 years ago, translation, In English

Hi there!

Today at 19:00 MSK will be held Topcoder SRM 685.

Let's discuss problems after contest!

  • Vote: I like it
  • +173
  • Vote: I do not like it

Comments Comments (36)
| Write comment?
»
9 years ago, # |
  Vote: I like it +94 Vote: I do not like it

Problem 450 is very creative:

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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) * N2 = NN which seems too big..

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

      I randomly generate a permutation of m edges and greedily (like Kruskal) find a spanning tree, then check if the remaining edges are valid. I do this for 300000 times and it passed ST. Maybe it's hard to generate testcases against this approach.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +35 Vote: I do not like it

        If there is a solution with 18 edges, then any random permutation where the 9 edges belonging to the first partition are before the 9 edges of the second partition works. The probability of getting permutation like this is at least . Therefore the probability of failing if you do 300000 iterations is at most .

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +197 Vote: I do not like it

      Since you only need two trees you can do this
      iterate through the edges and hold 2 dsu's
      assume that the edge is u-v if find(u, firstdsu) == find(v, firstdsu) then we do not need this edge in the firstdsu and we will use it in the second dsu
      likewise if find(u, seconddsu) == find(v, seconddsu) we just merge(u, v) in the first dsu
      if neither of these happen we just check the both ways (adding the edge in the first dsu or the second one) since this doesnt happen more than 2 ^ (2n — 2) (the number of times we get an edge that reduces the number of components) times we can say the program is of O(2 ^ (2n — 2) * m * dsuOperation)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +46 Vote: I do not like it

        I just have to comment by saying this is an awesome solution. It almost makes me not angry by the fact that this was a googleable problem :P

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          thanks that makes me pretty happy :D

          → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Didn't understand :| A little explanation please?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          i edited my explanation maybe it was because of the typo's (either -> neither) if you wanted more explanations please tell

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      I believe the intended solution is bell-number DP.

      For example, dp[{{1, 3, 6}, {2, 5}, {0}}] is true iff we can divide edges among {0, 1, 2, 3, 5, 6} into two groups such that

      • In the first group, all current vertices (0, 1, 2, 3, 5, 6) are connected.
      • In the second group, there are three connected components: {1, 3, 6}, {2, 5}, {0}.

      This solution will work in O(bell_number(N) * poly(N)).

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +30 Vote: I do not like it

      Hmm, I'm a bit surprised that no one mentioned the intended solution. Note that both testers come up with that first. (EDIT: it was mentioned above by Reyna)

      Consider edges one by one, each time you have 2 choices: add it to graph 1 or graph 2.

      Note that if add it to graph 1 no longer reduce the number of connected components, but add it to graph 2 can reduce the number of connected components, then we just add it to graph 2.

      With this pruning, the running time will be O(C(2n, n) * m).

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        This was mentioned above by Reyna and it think it's pretty cool.

        However, I'm wondering whether anyone tried to google this problem during testing?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          I Googled it with keywords like "split graph into two connected graphs" and so on, instead of searching things related to "spanning tree".

          → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +48 Vote: I do not like it

        If I understand correctly, the problem was to find 2 non-intersecting trees in a graph. It can be solved in polynomial time. Moreover, finding k non-intersecting trees can be done in time of (nk)^3.

        We can think in a problem in such way. Lets color each edge in it's own color, and copy graph k times. Then we need to find acyclic subgraph in which all colors are different. Both this conditions on sets form a matroid.

        We can find biggest set which lies in two matroids using matroid intersection algorithm

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

    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.
    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Looks like problem setter was studying spanning tree theorems when he came up with this round...

For div1 450, I thought about partitioning, but I only considered partitions into 2 sets and checking if edges between partitions were at least 2, not all partitions... I doubt I would be convinced that it would work even if I thought of the all partitions idea.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to check who is the author of this contest? It contained some graph problems that I found very interesting, so I want to check his previous rounds on CF/TC.

→ Reply
»
9 years ago, # |
  Vote: I like it +56 Vote: I do not like it

The hard problem is exactly the same as this one(in Chinese).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

cgy4ever What is the problem in running simple dfs for div 2 500 ? My solution with simple dfs. I find many submissions getting wrong answer for this. Can you please explain what is the right approach for this problem ?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 6   Vote: I like it +6 Vote: I do not like it

    "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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Could you solve this problem by using Dijkstra's algorithm on the first graph, then follow the same path for the second graph?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Shortest path in one graph will not lead to optimal answer (least product of total path length in two graphs). Hence this strategy won't work. As the constraints were small, I used floyd-warshall algorithm to solve it.

        for(from=0;from<vertices;from++)
    for(to=0;to<vertices;to++)
        for(via=0;via<vertices;via++)
            if(w1[from][to] * w2[from][to] > 
                 (w1[from][via]+w1[via][to]) * 
                     (w2[from][via]+w2[via][to])){
                w1[from][to]=w1[from][via]+w1[via][to];
                w2[from][to]=w2[from][via]+w2[via][to]; 
            }
ans=w1[0][1] * w2[0][1];
        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where does one public editorials on topcoder.com ?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody please explain, how to solve div 2 900?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Does anybody have the solution for div1 hard which he can prove?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +5 Vote: I do not like it

    Can anybody tell the idea of the problem?

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

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    Let g be the primitive root of 109 + 7.

    For each x = g0, g1, ..., g29999 and x = g0, g30000, ..., g999990000 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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +15 Vote: I do not like it

      Yes, that would lead to a proof that is 'not too long'. (obviously you can run your program for all 109 + 7 inputs to get a proof, but it may take years.)

      My proof is like this:

      1. Generate 20000 random graph with 10 nodes, for each of them compute Discrete logarithm of number of MST, so we get a list of 20000 numbers.

      2. Then for each pair of number in this list, add sum to a new list, so we get a new list of 200002 numbers.

      3. Find the minimal gaps between numbers in that list. In my case, it is 118.

      4. So my graph will have no more than 10 + 10 + (118/3) * 5 + (118%3) * 5 = 220 nodes. (A cycle with length 5 has g1 MST, and a clique of size 5 has g3 MST)

      My program needs to run about 2 minutes with 2GB of memory.

      → Reply