Interactive and Communication Problems

Author: Andi Qu

Some tips and tricks

In this module, we assume that "interactive" means problems that allow a limited number of queries and "communication" means problems about communicating between two separate programs.

Interactive Problems

Tip 1: Exploit the Limits

Since almost all interactive problems have a limit on the number of queries you may ask, you should use that limit to guide your thinking. There's no point in trying to come up with a solution that uses logN\log N queries when the limit is N2N^2!

There are three types of interactive problems:

  1. Problems that directly tell you the target complexity of your solution (e.g. IOI 2014 Rail).
  2. Problems that only tell you the maximum number of queries you may use (e.g. IOI 2013 Cave).
  3. Problems that have a hidden limit on the number of queries (e.g. IOI 2015 Scales).

The first type is nice because we get an idea of what our solution should look like.

The second type is slightly less nice, but we can still approximate the target complexity (e.g. N=5000N = 5000 and Q=70000    NlogNQ = 70000 \implies N \log N queries).

The third type is the least nice, but fortunately, we can sometimes still figure out the hidden limit. For example, in problems with relative scoring (like IOI 2015 Scales), we can submit a solution that uses a fixed number of queries for each input and then reverse-engineer the limit from our score.

Tip 2: Divide and Conquer

In most interactive problems, the solution is to divide and conquer. This is usually either binary search (logN\log N queries) or something like merge sort (NlogNN \log N queries)

Whenever you see large input limits and small query limits, you should immediately think of binary search.

Focus Problem – read through this problem before continuing!

In this problem, we have N=512N = 512 and Q9Q \leq 9. Notice how 29=5122^9 = 512 - this suggests that we should binary search.

Indeed, that's the solution - try to come up with it yourself!



Communication Problems

Tip 1: Don't Send Everything

Don't worry about not being able to send all the available information - in most cases, you shouldn't be able to!

Focus Problem – read through this problem before continuing!

In this problem, we're asked to store and compare an integer with several other integers.

Since these numbers can go up to 21212^{12} - 1, we can't just naively store and access AA (since that would take 24 operations).

Luckily, we can still store sufficient information about AA - just not in binary!


Tip 2: Brute Force

Sometimes, the amount of information that we can send is (slightly) more than the amount of information we need to decode.

In this case, we can simply map each piece of information we want to decode to a piece of information that we can send.

Focus Problem – read through this problem before continuing!

In this problem, we want to encode and decode an array of 64 integers less than 256 using an unordered sequence of 320 integers less than 256.

The number of arrays of 64 integers less than 256 is slightly less than the number of increasing sequences of 320 integers less than 256, so we can just map each array to an increasing sequence (using bignums) and send that sequence.

Tip 3: XOR

XOR has a nice property where ABA=BA \oplus B \oplus A = B. This lets us solve many problems where the data sent is corrupted or the receiver doesn't know what data the sender sent.

Focus Problem – read through this problem before continuing!



CEOI tasks can be found here.

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on Interactive and Communication Problems!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.