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

Could you help me with this strings problem?
Автор dcordb, 10 лет назад, По-английски

This is a problem from COCI 2003, here I left you the link. The problem name is VOKI (it is the third in the pdf).

http://hsin.hr/2003/national/second_day/juniors/problems.pdf

So far I have a DP approach that works in O(n * m * max(n, m)) which is too slow, could you help me to improve this?

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

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

What I understood from the problem is find the shortest sequence that exists in VOKI and dose not exist in TOKI.

It can be done in O(n * m * logm ) whenever you decide to include the ith letter of VOKI , do binary search to find the same letter in TOKI after or equal the jth letter . here is my solution http://ideone.com/bMBs68

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Can be done in O(n * m) also now nxt[i][j] denotes the next appearance of the ith letter after or equal to the jth index

    http://ideone.com/chXExW

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

    Could you explain it a little more? What I don't get is how do you guarantee that the subsequence isn't in TOKI. Also from your solution i and j are prefixes of VOKI and TOKI, right?

    → Ответить