I found this problem on URI online judge. I am getting 30% WA when I set T=1 and TLE on all other cases. I am using Tries to solve it. Is there a different approach to solve this problem?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:54:25
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:54:25
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 01:40:36 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
I have just sent a solution and got AC after I'd got TLE because it seems that we souldn't deal with the test cases ourselves, and should just write a program for one test case.
So, thank you for sharing this problem, and here are some hints which may help:
Let
lenbe the length of the given strings, andnbe a positive integer number.In the worst case (len = 10^5), what is the smallest
nwheressurely can't contains all the binary cases of lengthn?For a clearer view about "binary cases": the binary cases of length 2 are these 4 cases: 00, 01, 10, 11.
In the string
s, how should we test the existence of all of the binary cases of some lengthn?Do we need to generate all of that binary cases then ask if it exists in
s?Let me know if you want to ask more or to see the code.