# | 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 |
# | 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 |
Name |
---|
Wow, this red-black problem is really great and its solution is impressive. As far as I understood, all the observations about borders and strings of k-1 characters are just to create an intuition and turn out to be rather useless in the final algorithm? If for a fixed first player's move we try second player's responses in order according to our heuristic belief of being good responses (probably firstly b+s, then r+s, then borderless or sth like rb+"first player's move with cut two characters"?), we will have good upper bounds quicker? Was that already taken into account in that solution?
Yes, it is necessary to get good upper bounds and truncate bad responses quicker.
I.e., in my implemented solution, the number of Aho-Corasick runs for each k grows like this:
Whereas if I remove the heuristic of checking possibly good answers first, it becomes
As you can see, it's 100x slower even for k=11, and the difference will likely grow.
By the way, to give credit where credit's due: I did not come up with that solution myself — I only came up with the heuristics and unsuccessfully tried to speed up the exhaustive search using them, but could not come up with this beautiful approach which I've learned in the editorial. Kudos to misof and other IPSC problemsetters!