→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
13:46:16
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
13:46:16
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.11.2024 03:48:46 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
Well, an interesting problem...
But I've mistaken with the solution: we should use a DP instead.
maybe you are right ，but it's still hard for me to think in that direction (DP)
You can solve it using DP. We trying to construct a palindrome, but we didn't know it's length. We know some prefix, and we interested only in it's last 7 characters, reversed prefix is suffix because it's palindrome. Each time we trying to add some string into prefix or into suffix. this string must be first unused (or last). we have to remember for each side (prefix and suffix) where was added string at previous step, to prevent "collisions" — situations when two strings coincide. State of dp is 7 last characters of prefix (it's reverse is prefix of suffix), index of first unused string, index of last unused string, and two additinal boolean parameters). Also, don't forget about situation when string placed into the middle of the palidrome, you can try to combine suffix and prefix, after described DP. parameter "7 last characters" can be only one of string from input, or it's reverse.
UPD: Described idea has complexity O(N^3), maybe we should use Dijkstra, to increase perfomance
UPD2: I was wrong, actually it's complexity is O(N^2) because for each (beginStr, lastStr) there is constant number of possible strings to be prefix.
UPD3: my solution
what's cL and cR in your code
"we have to remember for each side (prefix and suffix) where was added string at previous step, to prevent “collisions” — situations when two strings coincide" cL == 1 iff there was string at very left of prefix (s), so we cannot add next string at pos = 0 (i = 0).
thank you , well I almost understand the solution except the "cL",I can't think it clearly ,can you show me an example about the use of cL ,maybe an example is helpful for me to understand ,thanks again
look at second sample — "abcdefg abcdefg".
L = 0, R = 2, s = "0123456"
at first step add abcdefg to the prefix at i=7.
L = 1, R = 2, s = "abcdefg"
you can't add next "abcdefg" at i=0, and go to L = 2, R = 2 because in this case answer will be abcdefgfedcba (both strings starts at the same place(at very begin of the string), but k[i] must be strictly less than k[i + 1].
another sample "abcdefg gfedcba" now you CAN add first string to the left, and then second string to the right. anwser abcdefgfedcba.
string added at previous step underlined
I still can't figure it out that why do you write (cR && i==0) its' the only question I have now
i don't know why name of variable is "cL", but you can read it as "can't to put string at very left". if cL == 1, you can't. if cL == 0 you can. look at picture again.
line 2: L = 1, R = 5, cL = 1, cR = 0
line 3: L = 1, R = 4, cL = 1, cR = 1
when we add string "bbbbaaa" to the right side at pos = 0 (i = 0), we should remember we still can't place string at left side. i.e.
cL && i == 0.