_ifahim1000_'s blog

Any tutorial on INTERACTIVE PROBLEMS?
By _ifahim1000_, history, 5 years ago, In English

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.me/blog/entry/45307

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

thanks in advance.

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

Comments Comments (2)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.)

→ Reply