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?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
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?
Название |
---|
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
len
be the length of the given strings
, andn
be a positive integer number.In the worst case (len = 10^5), what is the smallest
n
wheres
surely 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.