### bensonlzl's blog

By bensonlzl, history, 7 months ago,

Hi Codeforces,

Interactive problems prop up regularly in Codeforces contests nowadays, and are a staple in IOI (2013 Cave, 2016 Messy, 2017 Prize and Simurgh, 2018 Combo and Highways). These sort of problems usually involve (1) something hidden that the solution needs to find in (2) a limited number of queries that provide specific information. Some of these are more ad-hoc than others that also incorporate more standard algorithms.

In the Singapore CP community, I make interactive problems every once in a while for the online judge that we use (no links because we prefer to keep it within SG :P). Here are some examples of interactive problems that I have made over the past year or so (without solutions)

Ping
Wires
Hunter
Trespasser

Usually when I make an interactive problem, I either start with some puzzle or some game and turn it into a problem. The problem evolves over time as I add and remove conditions until I reach a problem that I am satisfied with.

To all the problem-setters out there that create and set interactive problems for various contests:

1. What are your thought processes as you start from an initial idea and end at the final problem?

2. What characteristics / ideas do you look out for in good interactive problems?

• +71

 » 7 months ago, # |   +53 Anything with binary search will do the job.:>
•  » » 7 months ago, # ^ |   -22 This is why I hate interactive problems. Most of them are divided into three groups: Binsearch (most popular, Hate) Guess the object (less popular, Tolerate) Game (rare, Don't like) It's too boring, I want something new! But I don't know what((
•  » » » 7 months ago, # ^ |   +8 I guess the idea behind most interactive problems is that you need to communicate with the grader to solve a problem, and the grader can give you the information you need to solve the problem. Consequently, it’s kind of unavoidable for interactive problems to ask you to find some hidden object.In most interactive problems, you are limited by the amount of information you can ask for, e.g. you can use at most $X$ queries etc. So naturally many problems involve something hidden that you need to find within the query limit, and a lot of times it happens that binary search is really good at doing that.Games are a bit more difficult to set because the grader often responds adaptively, i.e its moves depend on yours. As such, there is often some underlying optimal strategy that needs to be found.Maybe people can make interactive problems that require more ad-hoc style of searching for the answer, where the method needed to find some part of the hidden object needs a complex list of steps that really brings out the nice properties of the problem.
•  » » » 7 months ago, # ^ |   +1 Can you provide link problem of "Guess the object" category
•  » » » » 7 months ago, # ^ |   +10
 » 7 months ago, # | ← Rev. 2 →   -65 this blog looks like #iwantcontribution lol :|, but okay.ngmh Be like: "Why set interactive when u can set syntax?"
 » 7 months ago, # | ← Rev. 2 →   -24 bensonlzl sg noi 2019 shuffle is a good example of an interactive :> :>
 » 7 months ago, # |   0 It would actually be an interesting problem to extend "Ping" into $N$-dimensional continuous space, where the coordinates can also be negative, and we neet to solve it in $N+1$ queries.This is possible in the 2-D plane with direct triangulation, but I'd like to see how it can be extended into multiple dimensions without messy casework.
•  » » 7 months ago, # ^ |   0 There's a simple way to do it even in $N$ queries. SpoilerAsk the following queries (example for $N=5$): 1st: 0 0 0 0 0 2nd: 1 0 0 0 0 3rd: 0 1 0 0 0 4th: 0 0 1 0 0 5th: 0 0 0 1 0 From first and $(j+1)$-st queries we can deduce the $j$-th coordinate of the result; the $N$-th coordinate can be computed using all remaining coordinates and the first query.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +13 I don't think that works. Let's say $N=2$: Program: 0 0 Grader: 1.118033988749 Program: 1 0 Grader: 1.118033988749 With the derived data, you can't distinguish if the point is on $(0.5,1)$ or $(0.5,-1)$.
•  » » » » 7 months ago, # ^ |   0 Ahhhh, I see, thanks! So it seems another query (e.g. 0 0 0 0 1) is needed to distinguish these two candidates? Nice.