Interactive problems were already involved in IOI in the last century. Although interactive problems have not appeared in contests below the provincial-selection level in recent years, two interactive problems, 《P5208[WC2019]I-kun's Store》 and 《P5473[NOI2019]I-kun's Expedition》, appeared consecutively in NOI-series contests in 2019. This may represent interactive problems returning to the NOI series.
Interactive problems do not require a very high level of prerequisite algorithms, and generally do not have strict time limits; the quality of a program often depends only on the query limit. Therefore, when learning interactive problems, it is recommended to progress gradually according to difficulty. If you intend to train algorithmic thinking rather than merely learn algorithms, solving interactive problems is an excellent method. Although interactive problems usually have relatively low requirements for the algorithms contestants have mastered, it is still recommended to master some advanced and provincial-selection algorithms before attempting interactive problems, because by then your algorithmic thinking and breadth of knowledge will have reached a certain level. For a basic introduction to interactive problems, see OI Wiki's Problem Type Introduction - Interactive Problems.
Special errors in interactive problems:
- Contestants need to flush the buffer after every output; otherwise, an Idleness limit exceeded error will occur. In addition, if a problem contains multiple test cases and the program can determine the answer before reading all the data, it must still read all the data; otherwise, input confusion will likewise cause ILE (multiple queries can be issued at once and all query responses received at once). Also, avoid using fast input whenever possible.
- If the program makes too many queries, Codeforces will return a Wrong Answer verdict (although the judging system will explain the reason for the Wrong Answer), while UVa will return a Protocol Limit Exceeded (PLE) verdict.
- If the program's interaction format is incorrect, UVa will return a Protocol Violation (PV) verdict.
Because input and output in interactive problems are relatively cumbersome, it is recommended to encapsulate the input and output functions separately.
If the problem setter provides a grader header file (for debugging grader interactive problems) or a checker program (for debugging stdio interactive problems) during a contest, debugging interactive problems is relatively simple, because differential testing of interactive problems is much more difficult than that of ordinary problems. Without testlib.h, a stdio interaction library for a problem with many interaction details generally has about 3k lines of code, and with an additional differential tester of 3k lines, implementing it takes at least one hour. However, whether or not a debugging program is available, debugging interactive-problem code often requires contestants to simulate the interaction process with the program. Therefore, interactive problems require contestants to design high-quality programs, try to ensure correctness on the first attempt, and possess strong static error-finding abilities.
Example problems:
- CF679A Bear and Prime 100
- CF843B Interactive LowerBound
- [UOJ206[APIO2016]Gap](http://uoj.ac/problem/206)
- CF750F New Year and Finding Roots
- UVa12731 Mysterious Space Station
CF679A Bear and Prime 100
Every prime has exactly two factors, so we can directly enumerate the factors of the number to guess. Since at most 20 queries are allowed, and when trying to factor a relatively large number (such as 92) we find that we may need to enumerate primes up to , we first sieve out the primes less than 50 and query all these numbers once each.
Since differential testing for this problem is relatively easy, we can simply try every number in the value range. We find that the program cannot handle squares of primes effectively. Therefore, we also include the squares of 2, 3, 5, and 7, namely 4, 9, 25, and 49, for a total of 19 numbers, which meets the requirements.
Reference code
#include <cstdio>
constexpr int prime[] = {2, 3, 4, 5, 7, 9, 11, 13, 17, 19,
23, 25, 29, 31, 37, 41, 43, 47, 49};
int cnt = 0;
char res[5];
int main() {
for (int i : prime) {
printf("%d\n", i);
fflush(stdout);
scanf("%s", res);
if (res[0] == 'y' && ++cnt == 2) return printf("composite"), 0;
}
printf("prime");
return 0;
}
CF843B Interactive LowerBound
The linked list has at most elements, but we can make only queries and can obtain only the next element of an element, so the ordinary method of traversing the entire linked list is not applicable. There is only one way to directly try to approach the position of the target element: scatter random points.
For , enumerate directly. When , scatter 1000 points directly. The expected distance between these points is then small, so we can start traversing forward from the maximum value less than ; it can be proved that we obtain the answer before reaching the next point. Once an element greater than or equal to is found during the traversal, we can directly determine the answer.
Although the overall idea is simple, it may be difficult to think of in practice if you have not studied imperfect randomized algorithms such as simulated annealing.
Also, because Codeforces has a hack mechanism, many people deliberately target code that does not initialize the random seed, so before the random_shuffle() function, srand((size_t)new char) needs to be used.
Reference code
#include <algorithm>
#include <cstdio>
#include <cstdlib>
constexpr int N = 50005;
int n, start, x;
int a[N];
int main() {
scanf("%d%d%d", &n, &start, &x);
if (n < 2000) {
int ans = 2e9;
for (int i = 1; i <= n; i++) {
printf("? %d\n", i), fflush(stdout);
int val, next;
scanf("%d%d", &val, &next);
if (val >= x) ans = std::min(ans, val);
}
if (ans == 2e9) ans = -1;
printf("! %d", ans), fflush(stdout);
} else {
srand((size_t) new char);
int p = start, ans = 0;
for (int i = 1; i <= n; i++) a[i] = i;
std::random_shuffle(a + 1, a + n + 1);
for (int i = 1; i <= 1000; i++) {
printf("? %d\n", a[i]), fflush(stdout);
int val, next;
scanf("%d%d", &val, &next);
if (val < x && val > ans) p = a[i], ans = val;
}
while (p != -1 && ans < x) {
printf("? %d\n", p), fflush(stdout);
int val, next;
scanf("%d%d", &val, &next);
ans = val;
p = next;
}
if (ans < x) ans = -1;
printf("! %d", ans), fflush(stdout);
}
return 0;
}
UOJ206[APIO2016]Gap
Discuss the two subtasks separately:
-
Query limit.
Consider the first query. Since we initially know nothing, we need to query the range to obtain the maximum and minimum values.
Since the query limit is exactly , consider how to obtain a value that has not been obtained before on every query, so that we can roughly obtain all the numbers in the sequence within the query limit. The method is also very simple: after querying , let the obtained values be ; then query next.
-
Query interval size limit.
Since the problem requires the sum of the numbers in the query intervals not to exceed , consider minimizing the query intervals. The method above is no longer applicable, because the sum of the numbers in its query intervals has order . We can consider binary-searching the value range, but this method is unreliable, and in the worst case it may be forced to . Therefore, we need a more effective way to partition the value range, avoiding repeatedly querying points in query intervals and wasting opportunities.
Since the answer cannot be less than , we can consider partitioning the value range according to this value. Let initially be 0 and initially be the value above; query each time and update , then use as the step size to increase .
However, this method also cannot be applied well to Subtask 1, because in the worst case many query ranges may contain no numbers at all.
Reference code
#include <algorithm>
#include <cstdio>
#include "gap.h"
long long findGap(int T, int N) {
static long long a[100005] = {}, ans = 0;
long long s = 0, t = 1e18, s1, t1;
if (T == 1) {
int l = 1, r = N;
while (l <= r) {
MinMax(s, t, &s1, &t1);
a[l++] = s1, a[r--] = t1;
s = s1 + 1, t = t1 - 1;
}
for (int i = 2; i <= N; i++) ans = std::max(ans, a[i] - a[i - 1]);
} else if (T == 2) {
MinMax(s, t, &s1, &t1);
ans = (t1 - s1) / (N - 1);
long long l = s1 + 1, r = t1, last = s1;
for (long long i = l; i <= r;) {
MinMax(i, i + ans, &s1, &t1);
i += ans + 1;
if (s1 != -1) ans = std::max(ans, s1 - last), last = t1;
}
}
return ans;
}
CF750F New Year and Finding Roots
Given the strict requirements of and at most queries, we need to maximize the use of the information obtained from visits as rigorously as possible.
When , we can enumerate by brute force directly. However, when , a highly efficient traversal algorithm is required.
Randomly scattering points is not a good method, because random scattering cannot determine whether we are sufficiently close to the root, and with purely random scattering, the probability of hitting the root at least once is ; even after excluding repeated points, the probability of hitting the root is still very small.
Since , and we do not know which side is closer to the root, consider the worst case: when , our traversal direction is away from the root for the first two traversals and toward the root for the third. Therefore, we must traverse in all three directions.
Consider the two traversal methods, bfs and dfs. Since the bfs search tree may be very large, we first consider dfs. Of course, if we know the current depth and the current depth is small enough that the size of the search tree within the depth range is no greater than the remaining number of queries, we can use bfs directly.
Knowing the current node's depth and the direction of the current traversal provides a great advantage. However, it is very difficult to know whether we are currently traversing toward the root or toward a leaf node. When using dfs, we know the current direction only after reaching the root () or a leaf node (). Therefore, we need to determine the current node's depth as much as possible, and cannot use a method similar to iterative deepening search that stops midway through the traversal.
Consider choosing an initial node at random; starting from the initial node may encounter the worst case above.
If , we can directly know the current node's depth.
If , the current node is the root.
If , we directly consider performing dfs in all three directions. Of these, two directions go directly toward leaf nodes, and their traversal paths have the same length; the other direction goes toward the root, but may accidentally go toward leaf nodes midway, making the traversal path longer. We can then calculate the current node's depth.
When or , we need to consider longer traversal paths. We can identify the point of minimum depth on the path (which must have a smaller depth than the initial node). If we mark visited nodes and do not traverse them again, there is only one traversal path starting from that node. Although this path may still lead toward a leaf node, it must likewise contain a node whose depth is smaller than that of the starting point, so we can continue repeating the above steps from this node.
Of course, when considering the worst case for (each time moving only one step toward the root, then immediately moving toward a leaf node), we find that if we use only dfs, the worst case requires queries. However, we already know the depth of the initial node, so we can calculate the depths of all traversed nodes and, based on the discussion of bfs at the beginning, determine whether we can use bfs directly from the point with minimum depth.
At this point, we can calculate that the worst case requires 17 queries. Therefore, consider removing one node from the search tree (based on the fact that dfs can only traverse blindly, we consider bfs): when performing bfs to depth , the search tree has at most nodes, and it may take queries to determine which node has exactly 2 neighbors. However, if we have already queried of these nodes, we know that the last node must be the root.
Thus, the optimal solution in the worst case is as follows: when , perform dfs from a leaf node, each time moving only one step toward the root and then immediately toward a leaf node. After 10 queries, the currently known node with minimum depth has depth 4. Since its parent is known, perform bfs directly from its parent (the search tree has depth 3 and nodes). During bfs, after making queries, determine that the last node in the bfs search tree is the root.
Thus, our algorithm can exactly meet the worst-case limit of 16 queries.
Reference code
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
constexpr int N = 256 + 5;
int T, h, chance;
bool ok;
vector<int> to[N], path;
bool read(int x) {
if (to[x].empty()) {
printf("? %d\n", x), fflush(stdout);
int k, t;
scanf("%d", &k);
if (k == 0) exit(0);
for (int i = 0; i < k; i++) {
scanf("%d", &t);
to[x].push_back(t);
}
if (k == 2) {
printf("! %d\n", x), fflush(stdout);
return ok = true;
}
chance--;
}
return false;
}
bool dfs(int x) {
if (to[x].empty()) path.push_back(x);
if (read(x)) return true;
for (int i : to[x])
if (to[i].empty()) return dfs(i);
return false;
}
void bfs(int s, int k) {
queue<int> q;
for (int i : to[s])
if (to[i].empty()) q.push(i);
for (int i = 1; i < k; i++) {
int x = q.front();
q.pop();
if (read(x)) return;
for (int j : to[x])
if (to[j].empty()) q.push(j);
}
for (int i = 1; i < k; i++) {
int x = q.front();
q.pop();
if (read(x)) return;
}
printf("! %d\n", q.front()), fflush(stdout);
}
int main() {
for (scanf("%d", &T); T--;) {
ok = false;
for (int i = 0; i < N; i++) to[i].clear();
chance = 16;
scanf("%d", &h);
if (h == 0) exit(0);
vector<int> long_path;
if (read(1)) continue;
int root, dep;
if (to[1].size() == 1)
root = 1, dep = h;
else {
for (int i : to[1]) {
path.clear();
if (dfs(i)) break;
if (path.size() > long_path.size()) swap(path, long_path);
}
if (ok) continue;
dep = h - (path.size() + long_path.size()) / 2;
root = long_path.at((long_path.size() - (h - dep)) - 1);
}
while ((1 << (dep - 1)) - 2 > chance) {
path.clear();
if (dfs(root)) break;
dep = h - (h - dep + path.size()) / 2;
root = path.at((path.size() - (h - dep)) - 1);
}
if (!ok) bfs(root, 1 << (dep - 2));
}
return 0;
}
UVa12731 Mysterious Space Station
Since the only feedback is whether the robot hits a wall while moving, we should consider walking as close to the wall as possible without letting the robot get lost. This has several benefits:
- When walking close to a wall, it is easy to know whether we will hit it, obtaining as much information as possible.
- Teleporters do not appear in cells next to walls, which can prevent the robot from getting lost.
Therefore, if we know that the robot may be at a certain position next to a wall and need to determine whether it really is at that position, we can use the “wall follower method” to determine whether it really is there. According to topology, in a maze whose two sides are both walls, if we enter from the entrance and always keep one hand on the same side wall, we are guaranteed to find the exit. Since the walls in this problem form a closed loop, simply following the path along the wall guarantees that we can return to the starting point without hitting a wall. In addition, since the path along the wall is the largest closed loop on the map, the actual code does not need to deliberately hit a wall to ensure that the robot is on the wall path; the wall path can be marked on the map. Moreover, once a wall is hit, we need to quickly return along the original path, which can reduce the number of steps while preventing the robot from getting lost.
From this, we can derive a trial-and-error method for determining whether the robot is at a particular cell: move the robot to the wall path without entering unknown cells or known teleporters, and then walk around the wall path once. If no wall is hit during this process, we can determine that the robot is indeed at the particular cell.
We can use the method above: first mark all unknown cells in the figure, then determine whether each unknown cell is a teleporter from top to bottom and from left to right. We can first move to above the unknown cell, then move down and left. Next, use the method above to determine whether the robot is to the left of the unknown cell. If not, the robot is not at the position where it should be, meaning that the unknown cell is a teleporter.
After finding the unknown cells, we need to determine the pairing relationship of the 2k unknown cells. The actual method is also very simple: brute-force pairing is sufficient. Since , at most trial-and-error procedures are needed. For comparison, determining all unknown cells in the figure requires at most trial-and-error procedures.
The code below can currently pass only the UOJ mirror problem: #247. Rujia Liu's Present 7 - Mysterious Space Station, and cannot pass the original UVa problem. Modifying Rujia Liu's official solution on UOJ still did not make it pass, and it is currently impossible to contact Rujia Liu. Therefore, the code below follows UOJ.
However, Rujia Liu's official solution is much higher quality than the code below. You can view the official solution that passed the UOJ mirror problem on UOJ. On the same data, the official solution uses far fewer moves.
Reference code
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#define Wall 0
#define Unknown 1
#define Space 2
#define Gate 3
#define Path 4
const int N = 20;
const int dir[8][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0},
{-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
const char dirs[5] = "ESWN";
int n, m, k;
int a[N][N], id[N][N];
struct point {
int x, y;
point(int x = 0, int y = 0) : x(x), y(y) {}
bool operator==(const point& tmp) const { return x == tmp.x && y == tmp.y; }
bool operator!=(const point& tmp) const { return !(*this == tmp); }
point side(int d) const { return point(x + dir[d][0], y + dir[d][1]); }
int check(int d) { return a[x + dir[d][0]][y + dir[d][1]]; }
int id() { return ::id[x][y]; }
} start;
std::vector<std::pair<point, int>> path;
std::pair<point, point> ans[N];
std::pair<point, bool> vis[N];
bool walk(int d) {
printf("MoveRobot %c\n", dirs[d]);
fflush(stdout);
int ret;
scanf("%d", &ret);
return ret;
}
bool walk(int d, std::stack<int>& st) {
if (walk(d)) {
st.push(d);
return true;
}
return false;
}
bool read() {
if (scanf("%d%d%d", &n, &m, &k) != 3) return false;
if (n == 0) return false;
memset(a, 0, sizeof(a));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
char c;
std::cin >> c;
if (c == 'S') start = point(i, j);
if (c == '*')
a[i][j] = Wall;
else
a[i][j] = Unknown;
}
return true;
}
void answer() {
for (int i = 0; i < k; i++)
printf("Answer %d %d\n", ans[i].first.id(), ans[i].second.id());
fflush(stdout);
}
// Wall follower method: since the Path next to the wall is a maximal closed loop,
// it is enough that no obstacle is hit while walking along the Path
void wall_follower_init(point x, int last, int wallside, point s) {
if (x == s && !path.empty()) return;
if (x.check(wallside) == Path) {
path.push_back(std::make_pair(x, wallside));
wall_follower_init(x.side(wallside), wallside, last ^ 2, s);
} else if (x.check(last) == Wall) {
for (int i = 0; i < 4; i++)
if (i != (last ^ 2) && x.check(i) != Wall) {
path.push_back(std::make_pair(x, i));
wall_follower_init(x.side(i), i, last, s);
return;
}
} else {
path.push_back(std::make_pair(x, last));
wall_follower_init(x.side(last), last, wallside, s);
}
}
void init() {
int cnt = 1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (a[i][j] == Unknown) {
id[i][j] = cnt++;
for (int k = 0; k < 8; k++)
if (point(i, j).check(k) == Wall) {
a[i][j] = Path;
break;
}
} else
id[i][j] = 0;
}
path.clear();
int wallside = 0, last = 0;
for (int i = 0; i < 4; i++)
if (start.check(i) == Wall) {
wallside = i;
break;
}
for (int i = 0; i < 4; i++)
if (start.check(i) == Path && i != (wallside ^ 2)) {
last = i;
break;
}
wall_follower_init(start, last, wallside, start);
}
void undo(std::stack<int>& st) {
while (!st.empty()) walk(st.top() ^ 2), st.pop();
}
bool wall_follower(point x) {
std::stack<int> st;
bool ok = true;
int i = 0;
while (i < path.size() && path[i].first != x) i++;
for (int j = i; ok && j < path.size(); j++) {
if (walk(path[j].second))
st.push(path[j].second);
else
ok = false;
}
for (int j = 0; ok && j < i; j++) {
if (walk(path[j].second))
st.push(path[j].second);
else
ok = false;
}
if (!ok) undo(st);
return ok;
}
// Determine the current position
// at x. Using the “feel-the-stones-to-cross-the-river” method, it is enough to move along directions that avoid obstacles, unknown cells, and teleporters until reaching
// Path. Used when finding teleporters and pairing teleporters.
void bfs(point s, point t, std::vector<int>& v) {
static int map[N][N] = {};
memset(map, -1, sizeof(map));
std::queue<point> q;
map[s.x][s.y] = 4;
q.push(s);
while (!q.empty()) {
point x = q.front();
q.pop();
if (x == t) break;
for (int i = 0; i < 4; i++) {
point y = x.side(i);
if ((x.check(i) == Path || x.check(i) == Space) && map[y.x][y.y] == -1) {
map[y.x][y.y] = i;
q.push(y);
}
}
}
for (point x = t; x != s; x = x.side(map[x.x][x.y] ^ 2)) {
v.push_back(map[x.x][x.y]);
}
std::reverse(v.begin(), v.end());
}
bool move(point s, point t, std::stack<int>& st) { // Used when approaching a teleporter
static std::vector<int> v;
v.clear();
bfs(s, t, v);
for (int i : v)
if (!walk(i, st)) return false;
return true;
}
// Move toward the wall as quickly as possible
bool make_sure(point x, int last) {
if (a[x.x][x.y] == Path) return wall_follower(x);
for (int i = 0; i < 4; i++)
if ((x.check(i) == Path || x.check(i) == Space) && i != (last ^ 2)) {
if (!walk(i)) return false;
bool ret = make_sure(x.side(i), i);
walk(i ^ 2);
return ret;
}
return false;
}
void find_gate() {
int cnt = 0;
std::stack<int> st;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (cnt == k * 2 && a[i][j] == Unknown)
a[i][j] = Space;
else if (a[i][j] == Unknown) {
bool ok = true;
if (!move(start, point(i - 1, j), st))
ok = false;
else if (!walk(1, st))
ok = false;
else if (!walk(2, st))
ok = false;
else if (!make_sure(point(i, j - 1), -1))
ok = false;
if (!ok) {
vis[cnt++] = std::make_pair(point(i, j), false);
a[i][j] = Gate;
for (int k = 0; k < 8; k++) {
point y = point(i, j).side(k);
if (point(i, j).check(k) == Unknown) a[y.x][y.y] = Space;
}
} else
a[i][j] = Space;
undo(st);
}
}
void make_gate_pair() {
int cnt = 0;
std::stack<int> st;
for (int i = 0; i < k * 2; i++)
if (!vis[i].second)
for (int j = 0; !vis[i].second && j < k * 2; j++)
if (j != i && !vis[j].second) {
bool ok = true;
if (!move(start, vis[i].first.side(2), st))
ok = false;
else if (!walk(0, st))
ok = false;
else if (!make_sure(vis[j].first.side(0), -1))
ok = false;
if (ok) {
ans[cnt++] = std::make_pair(vis[i].first, vis[j].first);
vis[i].second = vis[j].second = true;
}
undo(st);
}
}
int main() {
while (read()) {
init();
find_gate();
make_gate_pair();
answer();
}
return 0;
}
Exercises
- Rujia Liu's Present 7 interactive-problem special contest is very high quality and highly recommended.
- P5473[NOI2019]I-kun's Expedition
- P5208[WC2019]I-kun's Store