PrevNext
Rare
 0/25

Interactive and Communication Problems

Author: Andi Qu

Some tips and tricks

Edit This Page

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 – try your best to solve 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!

Solution

The solution is to binary search on the DFS order of the tree for the largest prefix without an easter egg. This works because any prefix of the DFS order is a connected component.

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> graph[513], ord;
void dfs(int node = 1, int parent = 0) {
ord.push_back(node);
for (int i : graph[node])
if (i != parent) dfs(i, node);

Problems

StatusSourceProblem NameDifficultyTags
IOIEasy
IOIEasy
IOINormal
IOINormal
APIONormal
CEOIHard
IOIHard
IOIHard
IOIVery Hard
IOIVery Hard
IOIVery Hard
APIOVery Hard

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 – try your best to solve 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!

Solution - cmp

Here's how our algorithm works:

  • Consider AA and BB in base 4
  • First, encode each prefix of AA (6 operations)
  • Next, binary search for the longest common prefix PP of AA and BB (3 operations)
    • If this prefix is of length 6, A=BA = B
  • Otherwise, consider the digit dd directly after this prefix for BB:
    • If d>1d > 1, then we only need to check whether 4P+34P + 3 is encoded
    • Otherwise, we only need to check whether 4P4P is encoded
    • Check whether it is and return the answer (1 operation)

This algorithm uses only 10 operations instead of our original 24 - a significant improvement!

#include "cmp.h"
int delta[6]{1, 4097, 5121, 5377, 5441, 5457};
void remember(int n) {
for (int i = 0; i < 6; i++) bit_set((n >> i * 2) + delta[i]);
}
int compare(int b) {
int l = 0, r = 6;

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 – try your best to solve 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 – try your best to solve this problem before continuing!

Solution - Coins

Let the XOR-sum of the positions with heads-up coins be XX. Notice how if we flip coin XcX \oplus c, then the new XOR-sum of the positions with heads-up coins is now cc.

This allows Shahrnaz to determine cc after Arnavaz flips exactly 1 coin!

#include "coins.h"
std::vector<int> coin_flips(std::vector<int> b, int c) {
std::vector<int> flips(1);
int xr = c;
for (int i = 0; i < b.size(); i++) { xr ^= b[i] * i; }
flips[0] = xr;
return flips;
}
int find_coin(std::vector<int> b) {
int xr = 0;
for (int i = 0; i < b.size(); i++) { xr ^= b[i] * i; }
return xr;
}

Problems

StatusSourceProblem NameDifficultyTags
IOIEasy
CEOINormal
JOINormal
IOINormal
IOINormal
JOINormal
JOIHard
JOIHard
JOIVery Hard

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!

PrevNext