Problem A. Shifts
Topics: dynamic programming.
Suppose that we are allowed to make left circular shifts as well as right ones.
Can you solve the problem in this case?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 156 |
3 | atcoder_official | 156 |
3 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Yandex.Algorithm 2017, third elimination round: editorial (with challenges, bells and whistles)
Topics: dynamic programming.
Suppose that we are allowed to make left circular shifts as well as right ones.
First of all, notice that making a shift is effectively moving a character to a different position in the string. Clearly, moving a character more than once makes no sense since we could have just moved it to its final destination instead without wasting any operations.
Now, consider the characters that are not moved by any operation made, and match them with their final destinations in the second string.
Since both sets have to respect their relative order, they have to form a common subsequence of the two strings.
Rev. | Язык | Кто | Когда | Δ | Комментарий | |
---|---|---|---|---|---|---|
ru1 |
![]() |
Endagorion | 2017-06-06 16:14:50 | 23910 | Первая редакция перевода на Русский | |
en10 |
![]() |
Endagorion | 2017-06-04 17:07:12 | 26 | (published) | |
en9 |
![]() |
Endagorion | 2017-06-04 17:05:38 | 33 | ||
en8 |
![]() |
Endagorion | 2017-06-04 17:04:45 | 10870 | Tiny change: 'ler>\n\n\n</spoiler>\n\n#### P' -> 'ler>\n\n\n#### P' | |
en7 |
![]() |
Endagorion | 2017-06-04 16:18:23 | 5367 | Tiny change: 'iler>\n\n<spoil' -> 'iler>\n\n</spoiler>\n\n\n<spoil' | |
en6 |
![]() |
Endagorion | 2017-06-04 13:51:43 | 1634 | Tiny change: '>\n$O(n^2 log n)$ ti' -> '>\n$O(n^2 \log n)$ ti' | |
en5 |
![]() |
Endagorion | 2017-06-04 13:15:00 | 22 | Tiny change: '0^9 + 7$) numbers that cons' -> '0^9 + 7$) positive numbers are there that cons' | |
en4 |
![]() |
Endagorion | 2017-06-04 13:14:11 | 506 | ||
en3 |
![]() |
Endagorion | 2017-06-04 13:08:22 | 2456 | Tiny change: '### Proble' -> '#### Proble' | |
en2 |
![]() |
Endagorion | 2017-06-04 11:50:31 | 6467 | Tiny change: 'r, to any $X$ we can pr' -> 'r, to any X we can pr' | |
en1 |
![]() |
Endagorion | 2017-06-04 10:31:12 | 960 | Initial revision (saved to drafts) |
Название |
---|