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?
→ Pay attention
Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 days
Register now »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 days
Register now »
*has extra registration
→ Top rated
| # | User | Rating |
|---|---|---|
| 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 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/19/2024 23:25:42 (l3).
Desktop version, switch to mobile version.
Supported by
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.