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^__^
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
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).
how to apply meet in the middle in this case? could you explain more? and Thanks!
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
Thanks bro!
.