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 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 | 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 | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
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.