chrome's blog

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

Hi there!

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

Let's discuss problems after contest!

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

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

Is https://arena.topcoder.com/ loading??

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

How to solve Div. 1 1000?

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

    Oops, I was wrong, we should fix the order of vertices, not edges. I'll try to explain more clear.

    Suppose we have some graph. Let's build it spanning tree adding edges in order (0, 1), (0, 2), ..., (0, n-1), (1, 2), ..., (n-2, n-1) (of course edge is added only if it's presented in graph and if it does not make a cycle). This is what I called lex-min MST. Clearly, all connected graphs are split into equivalency components such that lex-min MST of all graphs from one component is the same.

    Now, let's fix some spanning tree with edges e1, ..., en - 1. count number of graphs with such lex-min MST. What can we say about such graphs? We know that edges e1, ..., en - 1 must be in the graph. More, for some other edges we know that they must not be in the graph, because otherwise lex-min MST would be different.

    So we have a problem: for each edge we either must include it, or must not, or this edge does not matter. In terms of problem it means that we should take a linear combination of input graphs such that on some positions there are 1-s and on some there are zeros. How to count them? Remove all columns corresponding to edges which we don't care for. Now check using Gauss method if we have at least one way to make this linear combination. If yes, total count is 2m - r, where m is the number of vectors (input graphs) and r is the rank of matrix with selected columns.

    The answer for the problem is sum of answers for all permutations of n vertices. Thus overall complexity is O(nn - 2·mn2) (because there are nn - 2 trees on n vertices). It probably won't fit into time limit so we should build trees recursively and do Gauss steps one by one in recursion.

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

      "Thus we fix a lex-min spanning tree". Can you explain this? You iterate over every possible spanning tree?

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

        I tried to explain a bit more clear in the update.

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

          Thanks a lot for explaining. I have one more doubt.How are you fixing the tree based on the ordering of vertices alone? It looks you are fixing that the tree must be a path to me.

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

            I was wrong again, sorry, fixed now. This is the solution described mostly by my teammate, at first I didn't understand him properly.

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

      I didn't get your solution, how can you know that some edges should be in the resulting graph? Two spanning trees can be valid and disjoint!

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

        If you build a spanning tree like in Kruskal algorithm adding edges in order I described then you'll get a unique spanning tree for each graph.

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

      My solution doing this runs in 1.9s on system tests.

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

        With doing one iteration of gauss on each step of recursion or without this optimize?

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

          Yes, I maintain the rows online in this bruteforce.

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

    Intended solution was to count for each partition number of subsets where there is no edges between different part. Then you can calculate the answer using exclusion formula.

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

      I was really surprised during contest that when I coded program to compute correct multiplicities it turned out that if I consider partition to k parts I have to multiply it by (k - 1)!( - 1)k - 1 :). I was rather expecting some random values. I really enjoyed solving this problem :).

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

How to solve Div 1 250?

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

    LCS is always n - 1, so you need to move one character so that the new string is also correct and it differs from original string. You can store all these strings in a set and the answer will be the size of the set.

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

How to solve Div2 1000?

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

    For each red player, find the maximum time till which it can play the game. To do that,Let

    dB[i] = Min time in which any player B can reach node i
    dA[i] = Time in which current red player under consideration can reach node i. 

    ans = INF
for every node u in A
   compute dA[] for node u
   currmax = 0
   for i in 0 to n
      if dA[i] < dB[i]  //Assume player u comes to this node and stands here till game ends
          currmax = max(currmax,dB[i])
   ans = min(ans,currmax)

    We basically try to find the minimum time till which all the red ones can survive in the game . To that for each red player we find the max time till which it can play the game and take min over all these.

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

    My idea is:We want to focus on a single red token,it doesn't matter a set of them,just one,so all blue tokens can focus on it and catch it.

    Ok.Now for this red token,we want a path so it resists maximal time.How does this path look?Like a normal path,because if we go on an edge,and come back from it,it's like staying.

    Good,so we fix a node to go (i is red token,j is final node).Now we also want to see if the red token,on it's way ,is safe(no blue token catches it before reaching j).

    This can be done with some array(dp[x]=minimal time for a blue token to reach x).And then for every node on path(excluding j,cuz already we want to catch i on j) we compare time[i][x] with dp[x].

    Taking into account all GOOD possible paths for i,we want the one with maximal time(to resist more).Take care that for a path(i going to j),the time to catch i is dp[j].

    Also from all red tokens,we choose one that we can catch fastest.

    Complexity O(n^3).

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

      my idea is the same during contest and passed. But i found a counterexample after that. if te tree is 1-2-3-4-5-6-7 and 1/7 is playerB and 4 is player A. The algorithm gives ans 3 but it should be 4. So i guess the system test cases may be very weak. Correct me if anything wrong

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

        Isn't the answer 3 only?

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

          aaaa yah im sorry i rethink the problem this morning and remember one player can move only ONE node once. I check the problem and found he can move SOME of the nodes

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

I am struggling with div1 250.

Correct solutions say that the answer for input string "((()))" is 3 and suggest strings "(()())", "(())()" and "()(())" as those that fulfil problem statement (here the length of lcs is 4).

Mine solution however apart from above mentioned strings gives me one more string, namely "()()()".

The question. Why string "()()()" does not fulfil problem statement?

Here is my code btw. The DP's state is (pos in string, balance between opened and closed brackets, length of lcs )

int yetanother2(string s) {
    int n = (int)s.size();
    int a[55];
    rep(i, n) a[i] = s[i] == '(' ? 0 : 1;
    CL(dp, 0);
    dp[0][0][0] = 1;

    rep(i, n) rep(j, n) rep(k, n) {
      if (!dp[i][j][k]) continue;
      rep(t, 2) {
        int dj = 1 - 2 * t;
        int nj = j + dj;
        if (nj < 0) continue;
        int dk = t == a[i] ? 1 : 0;
        int nk = k + dk;
        dp[i + 1][nj][nk] += dp[i][j][k];
      }
    }
    for (int i = n - 1; i >= 0; --i) {
      int s = dp[n][0][i];
      cout << s << endl;
      if (s) {
        return s;
      }
    }
    return 0;
  }
→ Reply