Interactive and Communication Problems

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 $\log N$ queries when the limit is $N^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 = 5000$ and $Q = 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 ($\log N$ queries) or something like merge sort ($N \log N$ queries)

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

In this problem, we have $N = 512$ and $Q \leq 9$. Notice how $2^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.

Copy
#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

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!

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

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

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

Solution - cmp

Here's how our algorithm works:

• Consider $A$ and $B$ in base 4
• First, encode each prefix of $A$ (6 operations)
• Next, binary search for the longest common prefix $P$ of $A$ and $B$ (3 operations)

  • If this prefix is of length 6, $A = B$
• Otherwise, consider the digit $d$ directly after this prefix for $B$:

  • If $d > 1$, then we only need to check whether $4P + 3$ is encoded
  • Otherwise, we only need to check whether $4P$ 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!

Copy
#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.

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 $A \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.

Solution - Coins

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

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

Copy
#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

CEOI tasks can be found here.