snowysecret's blog

By snowysecret, history, 4 years ago, In English

In some recent CF problems such as 1503B - 3-раскраска, it was mentioned that the interactor is adaptive. Are there any general methods to write adaptive interactors, or does it depend on the problem? Can anyone who has experience writing adaptive interactors share some of your thoughts? Thanks!

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

»
4 years ago, # |
  Vote: I like it +65 Vote: I do not like it

It depends on the problem. In this example, it is a game problem, so the interactor should be designed around a good strategy for Alice. I did this by checking for certain winning conditions, then forcing a win in such cases.

In many problems not about games, it's probably stated that there is some hidden information from you and the contestant must correctly guess something about this hidden information (say, an array) from queries. To make an adaptive interactor, it should keep in mind the set of all possible arrays that are consistent with the previous answers. Then when it's time to answer one of the contestant's queries, it should choose an answer consistent with at least one array in the set of possible arrays, and it should prefer an answer that makes it harder for the contestant. For example, it might be the most common answer of all possible arrays or an answer that requires the most additional queries.

In practice, it can be very hard to maintain the exact set of all answers consistent with the previous queries, and it can also be hard to decide exactly how the interactor should respond to queries to make it hardest for the contestant. Much of this is specific to the problem and up to the author.