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

Автор _ifahim1000_, история, 5 лет назад, По-английски

i want to learn how to solve interactive problems as i stuck on onsite contests earlier and "#codeforces 610" is going to have a such problem.

here is MikeMirzayanov blog...which is really helpful. https://codeforces.net/blog/entry/45307

so, i want to know more about how to crack these problems?

thanks in advance.

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There is no "general patterns" to solve interactive problems. Interactive is just another way of input/output for problems: you give the judge some output, the judge answers you back with some input. You have to cleverly choose your output to get the answer you want from the judge.

Codeforces has an "interactive" problem tag which you can practice to familiarize yourself more. After that it should mostly be treated as a normal problem.

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Here's a link to a contest with some interactive problems to try.

In general, many interactive tasks rely either on some form of binary search or on randomized algorithms, so it probably makes sense to start by considering these approaches. Randomized algorithms are especially useful on problems where it seems like you couldn't possibly have enough information to compute an answer. (One educational example is here.)