Alex7's blog

How to solve ICPC 2016 problem K with regular expressions?
By Alex7, 8 years ago, In English

So I solved problem K using DP, but the tutorial video said that some contestants managed to solve it with regular expressions.

However, the K-quotation in general is a context free grammar not a regular expression. I guess if you fix K it will become a regular expression but the length will grow too fast as K grows and since matching it requires 2^(len of expression) preprocessing I don't see a realistic way of doing it.

How did they manage to use regular expressions to solve the problem??? problem link, solution video

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

»
8 years ago, # |
  Vote: I like it -36 Vote: I do not like it

??? is very annoying. Consider writing one question mark next time.

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

    Thanks for the help your solution is brilliant man :v

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

I have problem understanding this statement, can you please tell me how the Output of second given test case came as 4?

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

    22 means 22 quotation marks in a row. Thus, this could be 4 quotes, 3 quotes, 2 quotes, 1 quote, 1quote, 1 quote, 1 quote, 2 quotes, 3 quotes, 4 quotes. (4 + 3 + 2 + 1 + 1 + 1 + 1 + 2 + 3 + 4 = 22), and this is a nesting with 4 layers.

    → Reply