Блог пользователя Alex7

Автор Alex7, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.