chrome's blog

Topcoder Open Algorithm Round 1C 2015
By chrome, 9 years ago, translation, In English

Hi there!

Tomorrow at 19:00 MSK will be held TCO15 Round 1C.

It is the last chance to advance to next stage.

The max. number of competitors is 2500. 750 of them advances to next stage.

Let's discuss problems after contest.

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

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

No Parallel Round?

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

What's the method for the last problem?

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

    Pretty simple dp problem.

    Dp with 4 parameters: dp[i][b][prev][len] — number of strings with length i having beauty b, last symbol prev and the length of suffix like 010101010 or 10101010 is len.

    There are solutions with 3 and 2 parameters, but the one with 4 parameters is the simpliest

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

Could someone explain as to how the solution to 450 was simply the number of leaves in the tree?

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

    Consider any path. When this path is included in the answer, a set of nodes can no longer be included. This always includes one or more leaves. Hence including each path makes 1 or more leaves ineligible for further inclusion. Hence the number of leaves is an upper bound on the answer. The way to realize this upper bound is to select all the leaves as 1 node paths.

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

I missed definition of Path in second problem, thus couldn't figure out for 15 minutes how Example 1 is possible. Path consisting of one node was not very canonical.

This was first round since last summer on Topcoder, so I had nice rating increase from 1375 to 1430. I think I should try shooting for yellow.

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

I solved 1000 using dp in O(cnt.n2). Is there any better solution ?

→ Reply