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?

Full text and comments »

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

By bensonlzl, history, 5 years ago, In English

I am currently working on the following problem:

  • Given a permutation $$$A$$$ of length $$$N$$$, you have $$$Q$$$ queries specifying 2 numbers $$$X$$$ and $$$Y$$$ that swap the elements at indices $$$X$$$ and $$$Y$$$. After every query, output the number of inversions in the new permutation. All queries must be answered online.

My current solution can process every query in $$$\log^2$$$ $$$N$$$ per query and $$$N$$$ $$$\log$$$ $$$N$$$ precomputation, by first precomputing the number of inversions in the initial permutation and using a segment tree with a BBST in every node. Each BBST stores all of the elements in the range covered by the segment tree node.

We perform a range query on the value at index $$$X$$$ and the value at index $$$Y$$$ to determine the number of numbers smaller than either number in the segment between them, and then compute the change in inversions. After that, we update the 2 indices in the segment tree. Each of the $$$\log$$$ $$$N$$$ nodes takes $$$\log$$$ $$$N$$$ time to update, which gives an overall complexity of $$$\log^2$$$ $$$N$$$.

My question is: Is it possible to compute the change in inversions more quickly than $$$\log^2$$$ $$$N$$$? eg. computing the change in $$$\log$$$ $$$N$$$ time. I suspect that it is possible with either a modification to the segment tree, or using a completely different data structure all together. Any ideas are welcome :)

Full text and comments »

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