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

hard question
Автор Eddagdeg, история, 6 лет назад, По-английски

Hello codeforces community! I'm stuck in this problem :you are given two strings s1 and s2 in one operation ou can reverse a substring in s2 what's the minimum number of operations needed to get identical strings.Opertations are made only on string 2? link Bonus:what's would be the answer if we can apply operations on both strings? any help! and Thanks^__^

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

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

I would try Meet in the middle technique. Note, that upperbound for the answer is 9, so it should pass time limits with some kind of memorization.

The answer would be the same if we could apply operation on both strings (it's trivial to prove if my approach described above is correct).

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

    how to apply meet in the middle in this case? could you explain more? and Thanks!

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

      You just run two BFSes from start and destination string with constraint of max. distance from source equals 4. You return a distance if two BFSes "overlap" or just 9, if not.

      Complexity is around O((n2)4) with fractional constant.

      My code (with lots of if-optimization and own hash function to pass tests): https://ideone.com/n5Y1Aj

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

.

→ Ответить