cgy4ever's blog

Topcoder SRM 698
By cgy4ever, history, 8 years ago, In English

Hi there,

Topcoder SRM 698 will start in about 9 hours (Sept 17, 12:00 noon EDT).

This round is Sponsored by Google, find more details here.

Thanks for participating! The Div1-Medium and Hard were prepared to be used in TCO Round 3B, but shangjingbo told me they are too easy (he got the idea for each of them in 10 minutes). It turns out they are not that easy. :P

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

Comments Comments (27)
| Write comment?
»
8 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Let me be the first one. How to solve Div1 Hard?

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

    spoiler

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

      let's spoil it :)

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

      I still don't follow. Can you explain further?

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

        I think there is one detail not obvious at first: 2-SAT solution may choose, for example, pieces like this:

        ##.   .##   ...   ...   ###
... + ... + #.. + ..# = #.#
...   ...   #..   ..#   #.#

        which is not a good shape, so one might think this solution is not really correct, but actually it doesn't matter because in every such case the resulting "bad" shape contains a good sub-shape, so if there is a solution with some "bad" shapes, then there is also a solution where all shapes are good.

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

          Thanks, that's the part I hadn't understood.

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

Anyone please explain the approach of Div2 hard...

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it
    Solution
    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    We can solve the problem for each bit, and then sum them up. For each bit, it becomes: compute the number of subtrees such that at least one node has weight 1. It equals to: (number of all subtree) — (number of subtree that all nodes has weight 0). Both can be solved by tree DP.

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

Div2 Hard ?

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

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

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

Lol, because someone got an idea in 10 minutes for that problem you put significantly easier problem on TCO xD. And hard looks pretty unsolvable during that time (just first impression). It has some flow flavor in its looks, but dunno.

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

    Yes, this Hard is not ideal: if you don't have a template for 2-SAT, then it will be too hard to code it in time. And it is vulnerable to bruteforce search.

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

Hints for Div1 500?

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

    Good pairs = all pairs — bad pairs.

    Pair is bad if at least one of sets has <3 points or if they form two legit polygons that have no intersection.

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

      Figured out this much. Can't figure out how to find the total number of possible non-intersecting pairs of polygons. Thanks for the help though!

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

        So now think how we can count legit nonintersecting polygonal. They can be separated by a line. It would be good to make that line unique.

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

Nice Contest :)

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

My screencast

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

SRM 698 Div 1 250 — link

SRM 497 Div 2 1000 — link

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

I haven't been able to participate in recent matches since hackerrank stopped showing SRM in it's calendar. What are other alternatives? How do you remember contests?

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

I cannot find the editorial.
How to solve the problem RepeatString?

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

    Break the string in two parts(there n-1 ways to it) and find it's LCS. Answer will be 2 * maximum of all those LCS.

    Complexity -> O(n^3)

    Code

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

      Is it possible to use here Minimum Edit Distance algorithm?
      The description of the algorithm looks suspiciously similar to the problem description. At least the algorithm supports the same kind of operations: insertion, deletion and substitution.

      → Reply