### Petr's blog

By Petr, history, 13 months ago, ,

•
• +55
•

 » 13 months ago, # |   +10 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?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +10 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: 1 4 2 8 3 17 4 28 5 59 6 177 7 464 8 692 9 6466 10 12164 11 4209 Whereas if I remove the heuristic of checking possibly good answers first, it becomes 1 1 2 4 3 17 4 48 5 203 6 800 7 2876 8 9898 9 44810 10 139152 11 409315 As you can see, it's 100x slower even for k=11, and the difference will likely grow.
•  » » 13 months ago, # ^ |   +28 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!