Petr's blog

By Petr, history, 3 months ago, In English,
 
 
 
 
  • Vote: I like it  
  • +55
  • Vote: I do not like it  

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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!