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 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.05.2024 20:21:31 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
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!
.