_ifahim1000_'s blog

By _ifahim1000_, history, 19 months 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.com/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

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _ifahim1000_ (previous revision, new revision, compare).

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

you may want to take a look at https://www.youtube.com/watch?v=GS2MxmorEzc. it contains a treatment of interactive problems, though the video by and large isn't specifically for them

»
19 months 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.

»
19 months 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.)