chrome's blog

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

Hi there!

Today Tomorrow at 20:00 MSK will be held Topcoder SRM 677.

Let's discuss problems after contest.

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

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

chrome is back !

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

Looking at the Topcoder Dashboard, it seems like Topcoder is making an attempt to improve user experience for good! The "Launch Arena" button also directly redirects to the web arena, instead of asking me to download an application.

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

    Is it possible to use something like KawigiEdit in WebArena to generate C++ source stub with tests?

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

      I am not sure if stable plugins are available for the Web Arena yet. This blogpost from Jan 2015 gives an impression that they're still testing some plugins.

      The web arena is open-source and available on Github, if anyone wants to contribute. I think they have some support for calling arena functions to generate code skeletons in various languages.

      EDIT: This commit (#c380ff) seems to have added support for the Web Arena Plugin API.

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

        I didn't imply a plugin for Web Arena.
        It would be enough for me to have any utility, which converts text problem statement into C++ source file template with class definition, tests and expected results check.

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

Bumping this, since it starts in about 12 hours from now.

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

I see. Your job here is to remind us about topcoder contests.

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

I can't open the Arena, anyone is experiencing the same issue?

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

    If only topcoder contests were made on Codeforces platform

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

What about Web Arena? Did someone use in recent matches? Were any bugs?

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

This will be my first match on TopCoder. I have few doubts.

  1. Will submission points decrease if my solution fails to compile or doesn't pass batch test?

  2. If i don't submit any problem's code then also my rating will be affected?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it
    1. No.
    2. Yes, but you should open at least one problem statement.
    → Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to do div1 500?

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

    DP[v][i][j] — probability that diameter of subtree rooted at v will be i and longest path from v to leaf of this subtree will be j.

    When you are merging two trees — you try both possible values for added edge; new deepest vertex is trivial, new diameter of subtree is either diameter of some of two old parts or path connecting deepest vertices in two parts (depending on which one is longer).

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

      I coded this idea but I got TLE since it's 50*100^4 steps, do you merge dp[v][i][j] and dp[child][i][j] in faster than 100^4?

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

        It's not more than 100^4. In fact constant behind it is also small. And I've just checked it in practice room, my solution runs in 0.005 seconds.

        You only need to implement your knapsack in not-so-careless way. At least do all cycles up to largest possible value at this moment, not up to 100.

        P.S. Actually I have no idea about number of reachable states here, maybe it works even in O(N^3), looking at running time of my code. However, for knapsack in general it will be N^4.

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

          I don't know what do you mean by not-so-careless, and I'm doing cycles up to largest possible value, but it's still very big number 100^4 * 50 equal to 5 *10^9, so it's hard to pass even with a lot of constant optimization

          here's my code http://pastebin.com/th0fb1KV which got TLE

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

            Instead of bounding values for both subtrees by size1+size2 or max(size1,size2) (which obviously gives you N^5 on chain graph), you have to bound values for first subtree by size1 and values for second subtree by size2. Here is a code.

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

              that magic if (dp[v][i][j]>1e-20) made my code very fast!!! but your code is fast even without it!

              I also had a bug that I am iterating to mx[nd]*2 which can become 200 (note that in my code mx[nd] is already multiplied by 2) so I changed it to min(100,mx[nd]*2)

              I will look through your code to know why it's fast

              thank you

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

              by the way this solution doesn't have the official intended complexity!

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

        Maintain another array depth[v]-maximum depth in subtree v.In DP[v][i][j] you can see that i can only go from depth[v] to min(depth[v]*4,2*(n-1)) and j go from depth[v] to 2*depth[v].So we can cut off many unused states.I got AC that way.

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

          I did what you said, I got AC but it barely fit the TL (running time is 1.8 s) also I had a bug in my code which made it running more steps and even going outside array bound

          thanks

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

    First for each subtree and each d between 0 and n calculate probability that subtrees depth will be at most d. Then choose center of graph and length of diameter. There are 2 cases: center is on vertex, or center is on edge. In first case depth of tree should be half of diameter and there should be at least 2 subtrees with that depth. In second case each end of our edge should have fixed depth, which depends on the position of center on edge and edge length.

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

Where is instant post-match editorial when you need it the most? ;_;

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

How to solve div2 Hard ?

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

    I had a weird DP solution for Div2 900

    Let dp(i,j) denote the length of smallest palindromic path between node-i and node-j

    Note that dp(i,j) = -1 if there is no pair (u,v) such that (u,i) and (v,j) are valid edges and label on (u,i) is equal to label on (v,j).

    The base cases will be:

    dp(i,j) = 0 if i==j (trivial)

    dp(i,j) = 1 if (i,j) have an edge between them.

    Now we can loop over all pairs (u,v) such that (u,i) and (v,j) are valid edges and label on (u,i) is equal to label on (v,j). Our answer for dp(i,j) will be 2+min(dp(u,v)) for all (u,v)

    Our final answer will be dp(0,1). Sample Code: Link

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

      I don't think it's a DP solution ! But the idea is really cool !

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

cgy4ever is the writer of this round. It seems he may be busy now, so I'll post solutions for him.

Here is code:

div2: http://pastebin.com/sgnpradR

div1: http://pastebin.com/PLHbRYF9

some hints:

  • div2 easy: just do what's described in the statement.
  • div2 med: 2 approaches 1) The string has length at most 40. Brute force 40^4 tuples of positions that the 4 strings can take on. 2) Try all orders of concatenating the string together (how do you merge two strings?)
  • div2 hard: Make a new graph where new vertices are a pair of original vertices. What are the edges in this new graph?
  • div1 easy: 2 approaches 1) Fix the number of multiply by 2 operations. Now, we can proceed greedily. 2) Work backwards (i.e. operations are divide by 2 or subtract 1).
  • div1 med: 2 approaches: 1) Root the tree arbitrarily. Compute prob(tree has diameter <= x) using a dp based on longest path to leaf. 2) Find the probability that the graph has a particular center and diameter. The center can either be a vertex or at the middle of an edge.
  • div1 hard: First, any strongly connected tournament graph has a hamiltonian cycle. Find any such one. Then, we can do bubble sort (see code for more details). (Tricky case for div1 hard. A cycle 0->1->...->29->0. All other edges go from bigger numbers to smaller numbers.)
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In div1 med center is not necessarily on middle of an edge. It be on distance 0.5 from one end and 1.5 from the other end.

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

Screencast

→ Reply