bensonlzl's blog

By bensonlzl, history, 5 years ago, In English

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?

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Anything with binary search will do the job.

:>

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    This is why I hate interactive problems. Most of them are divided into three groups:

    1. Binsearch (most popular, Hate)

    2. Guess the object (less popular, Tolerate)

    3. Game (rare, Don't like)

    It's too boring, I want something new! But I don't know what((

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Can you provide link problem of "Guess the object" category

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There's a simple way to do it even in $$$N$$$ queries.

    Spoiler
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ahhhh, I see, thanks! So it seems another query (e.g. 0 0 0 0 1) is needed to distinguish these two candidates? Nice.