Eddagdeg's blog

hard question
By Eddagdeg, history, 6 years ago, In English

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^__^

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

»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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).

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

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

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

      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

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

.

→ Reply