Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя Petr

A red-black week
Автор Petr, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +55
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +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?

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← 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.

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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!

    → Ответить