Petr's blog

A red-black week
By Petr, history, 7 years ago, In English

http://petr-mitrichev.blogspot.com/2017/07/a-red-black-week.html

  • Vote: I like it
  • +55
  • Vote: I do not like it

»
7 years 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?

→ Reply
  • »
    »
    7 years 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.

    → Reply
  • »
    »
    7 years 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!

    → Reply