Interactive Algorithms – Tasks with Queries
In this section you will find tasks of the interactive type, worked out in detail — problems in which your program asks queries, waits for the answers and adapts its strategy while it runs. Interactive algorithms are an important part of competitions and need careful planning of the number of queries, building tests that tell cases apart, and robustness against unexpected answers.
Note: the tasks on this page are taken from the collection Kilonova — Interactive Problems List. All the tasks here are worked out with explanations and solutions.
Going through the tasks with interactive algorithms helps you master the following concepts:
- The interaction protocol: how to ask questions and process the answers.
- Binary search in interactive mode.
- Strategies for robustness against random or variable answers (e.g. majority voting, repeating queries).
- Combining queries to locate the target segment or position.
Every task is presented with a complete hint, ideas for solving it and ready-made code — ideal for learning and practising strategic techniques in interactive conditions.
Task 1 – A game with the Joker
Problem description
The players play a game with the Joker. He gave them a number N (5 ≤ N ≤ 1000) and told them that he has hidden two numbers L and R (0 ≤ L ≤ R ≤ N−1). The goal of the game is for the players to find those two numbers.
The players may ask questions of the following form: they give an array of N numbers a_0, a_1, …, a_{N−1} and ask: "Tell me the minimum of the numbers aL, aL+1, …, aR."
The problem is that the Joker's language has no word for minimum — he understands the word extreme, so to every question he randomly answers with either the minimum or the maximum of the segment [L,R] of the array.
The Joker accepts as a correct answer every guess (L', R') that satisfies:
|L − L'| + |R − R'| ≤ 1
Task
Based on this information, the players need to find a pair (L', R') that the Joker considers correct, using as few questions as possible.
Specification
- Time limit: 1 second
- Memory limit: 1024 MB
- Input:
stdin - Output:
stdout
Interaction
The players can use the following functions to interact with the Joker:
int query(std::vector<int> a)– takes an array of numbers and returns either the minimum or the maximum of the segment[L,R], chosen randomly by the Joker.void answer(int L, int R)– is called with the guessed pair(L,R)that the players consider correct.
The players need to implement only the function solve(int N). There is no need to implement the main function. All the code is written in the file solutie.cpp. The players may also define extra functions and global variables.
An example of interaction
Example: N = 5, the hidden numbers L = 1, R = 3. The segment [L,R] matches the array {3, 8, 1}.
If the players call:
int res = query({5, 3, 8, 1, 6});
the Joker returns either 1 (the minimum) or 8 (the maximum).
If the players call:
answer(1, 3);
this is shown:
Correct
For a more detailed solution and explanation of the task Joker, read the whole page with the solution .
Task 2 – Plockchain and Lina
Vasilije is Lina's friend. Recently he opened an account on Pinance so that he could spend more time investing in cryptocurrencies than in church. To his surprise, one day he noticed that his investments had paid off. Taken aback by this, he decided to analyse the events that took place in the Plockchain and brought him to these heights.
Vasilije explained to us that we can imagine that the Plockchain works as follows:
- At the beginning there are N transaction requests in the system, indexed from 1 to N. Every request i has a fee Wi and a unique request it directly depends on, Pi.
- The request with the index 1 is said to be the original one and it has no dependency.
Vasilije noticed that three types of operations happen in the Plockchain:
- A new request appears with the fee C, whose direct dependency is T. The index of that request will be N + t + 1, where t is the number of requests added this way so far. So the first added request gets the index N + 1.
- The fee of the request with the index a changes from Wa to C.
- The request with the index a is deleted. It is guaranteed that there is no request j such that Pj = a (that is, no request depends on it).
Lina, amazed by Vasilije's explanations, started to ask the following question often:
"If we look at all the requests that are in the system at the moment, how big a fee would a hacker get if they executed all the requests that are at most H levels of dependency below the request X?"
We say that a request A is at most x dependencies below B if and only if:
- x ≥ 0 and A = B, or
- x ≥ 1 and PA is at most x - 1 dependencies below B.
We assume that the hacker gets the sum of the fees of all the executed requests. Lina's questions do not change the state of the system. Also, the constant H is the same for every question.
Task
You need to find the answers to the questions Lina asks after a series of operations.
Input
- The first line: N, Q and H – the number of initial requests, the number of operations and the constant H.
- The second line: N numbers – the fees Wi for every request.
- The third line: N - 1 numbers – Pi+1, the request on which the request i+1 depends.
- Then Q lines follow – every operation has the form:
- t = 1:
C T(a new request with a fee and a dependency) - t = 2:
a M(the fee of the request a changes) - t = 3:
a(the request a is deleted) - t = 4:
X(Lina's question for the request X)
- t = 1:
Output
For every question (an operation with t = 4) print the total sum of the fees for the matching requests.
Constraints
- 2 ≤ N ≤ 200 000
- 1 ≤ Q ≤ 200 000
- 1 ≤ H ≤ N
- 0 ≤ C, M ≤ 1 000 000 000
- T < R when a new request is added
- 1 ≤ Pi < i
- 0 ≤ Wi ≤ 1 000 000 000
- The requests in the operations always exist at that moment
- The request 1 is never deleted
- A request on which some other request depends is never deleted
Example
stdin:
8 7 2
10 12 4 20 4 5 11 10
1 1 3 4 2 6 6
1 50 4
4 3
2 1 50
4 1
2 6 35
1 5 7
4 6
stdout:
78
91
61
Explanation
For the first question, the requests that are at most 2 levels of dependency below the request 3 are: 3 (fee 4), 4 (20), 9 (50), 5 (4). In total: 4 + 20 + 50 + 4 = 78.
Task 3 – Paint
Problem description
Time limit: 1s
Memory limit: 512MB
Input: stdin
Output: stdout
You have a collection of n containers, each holding x_i litres of paint. You have q types of buckets available, where a bucket of type i holds exactly y_i litres. There are infinitely many buckets of every type.
To make new shades, you can choose any contiguous subsequence of containers and mix the paint from them. Then you choose one type of bucket and check whether you can pack all the paint you got using only buckets of that type (with nothing left over).
Task
For every type of bucket, determine in how many ways a subsequence of containers can be chosen so that the total amount of paint can be packed completely into buckets of that type.
Input
The first line: two integers n and q
The second line: n numbers x₁, x₂, …, xₙ
The third line: q numbers y₁, y₂, …, y_q
Output
The program prints q lines — for every bucket the number of subsequences that can be packed completely.
Constraints
1 ≤ N, Q ≤ 80001 ≤ x_i, y_i ≤ 10⁶
Subtasks
- (10 points)
q = 1andy₁ > Σx_i - (20 points)
N ≤ 60, Q ≤ 100 - (30 points)
N ≤ 500, Q ≤ 1000 - (40 points) No extra constraints
Example
Input
5 2
4 2 3 6 8
4 5
Output
2
2
For a more detailed solution and explanation of the task Paint, read the whole page with the solution .
Task 4 – Maximising BTC through crypto trading
Time limit: 2s
Memory limit: 512MB
Input: stdin
Output: stdout
Problem description
Alex starts with exactly 1 BTC and wants to increase his capital over a series of N trading days.
On the platform there are K cryptocurrencies, numbered from 1 to K, where
1 is reserved for BTC.
Every day he gets a K × K matrix A, where A[i][j] is the rate
at which he can convert an amount x in the currency i into A[i][j] * x of the currency
j. Every transaction takes one whole day, so funds converted today cannot be used again on the same day.
Alex may also decide not to make any transaction on that day.
After N days Alex wants to end up with the maximum amount of BTC. You need to determine that maximum amount.
Input
- The first line:
NandK, the number of days and the number of cryptocurrencies. - Then
Nmatrices of sizeK × Kof real numbers follow, whereA[i][j]is the conversion rate.
Output
Print a real number — the maximum amount of BTC Alex can have after N days. The answer must have a relative error of at most 10-6.
Constraints
1 ≤ N ≤ 801 ≤ K ≤ 5010-5 < A[i][j] < 105x ≤ 1013
Example
Input:
1 3
2.0 1.0 2.5
1.4 1.0 3.14159265359
3.0 3.0 3.0
Output:
2.0000000000
Explanation of the example
In the example there is one day and three currencies. If Alex uses today's rates directly for BTC→BTC with the factor 2.0,
his amount of BTC will grow from 1 to 2 BTC. In this example that is optimal.
For a more detailed solution and explanation of the task Maximising BTC through crypto trading, read the whole page with the solution .
Task 5 – Symmetric filling
Time limit: 0.2s Memory limit: 256MB
Input: stdin Output: stdout
Problem description
Miša got a set of N × M glasses from Saint Nicholas, and he arranged them in the shape of a matrix with N rows and M columns.
He has two types of milk available in unlimited amounts: milk A and milk B.
Every glass can be filled with either milk A or milk B. Let L[i][j] denote the type of milk in the glass at the position
(i, j).
Miša wants to know in how many different ways he can fill all N × M glasses, if he must respect Q constraints of the following type:
Every constraint is given by four numbers a b c d and represents a submatrix determined by:
- the lower left corner at the position
(a, b), - the upper right corner at the position
(c, d).
In every submatrix the glasses must form a picture that is symmetric with respect to the horizontal and the vertical axis. Formally:
L[a + i][j] = L[c - i][j]for every0 ≤ i ≤ c − aandb ≤ j ≤ d.L[i][b + j] = L[i][d - j]for everya ≤ i ≤ cand0 ≤ j ≤ d − b.
You need to calculate the number of ways to fill all the glasses so that all the constraints are met. Give the result modulo 998244353.
Input
- The first line: three integers
N M Q— the number of rows, the number of columns and the number of constraints. - The next
Qlines: four integers each,a b c d— the coordinates of the lower left and the upper right corner of the submatrix.
Output
Print one integer: the number of ways to fill the glasses while respecting all the constraints, modulo 998244353.
Constraints
- 1 ≤ N, M ≤ 300
- 1 ≤ Q ≤ 30000
- 1 ≤ a ≤ c ≤ N
- 1 ≤ b ≤ d ≤ M
Subtasks
| # | Points | Constraint |
|---|---|---|
| 0 | 0 | Examples only |
| 1 | 11 | N = 1 |
| 2 | 13 | The submatrices do not overlap |
| 3 | 32 | Σ (c_i − a_i + 1)·(d_i − b_i + 1) ≤ 200000 |
| 4 | 44 | No extra constraints |
Example 1
stdin 4 5 2 1 2 3 4 1 1 4 5 stdout 16
Example 2
stdin 10 10 3 1 1 4 4 5 5 10 10 8 1 10 3 stdout 229805564
Hint — the idea of the solution
- Every constraint imposes equivalence conditions between the cells of the matrix (they must have the same type of milk).
- The problem comes down to determining the number of different equivalence classes over the cells.
- For every class we can independently choose whether it will contain milk A or B.
- So the answer is
2^(number_of_classes)mod998244353. - In the implementation a DSU (Union-Find) structure is used to join the cells that must be equal.
Solution (C++)
// Symmetric filling — the DSU (Union-Find) approach
// The idea:
// Every constraint imposes equalities between certain cells.
// These equalities are modelled with a DSU structure.
// Every independent DSU component can be A or B → 2 choices.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
/*
* DSU (Disjoint Set Union) structure
* p[x] – the parent of the node x
* sz[x] – the size of the component (used for union by size)
*/
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n), sz(n, 1) {
iota(p.begin(), p.end(), 0);
}
// Finding the representative of a set (path compression)
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]);
}
// Joining two sets
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
// The smaller set is attached to the larger one
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, Q;
cin >> N >> M >> Q;
int total = N * M;
DSU dsu(total);
// Mapping the 2D coordinates (i, j) to a 1D index
auto id = [&](int i, int j) {
return (i - 1) * M + (j - 1);
};
// Processing all the constraints
for (int q = 0; q < Q; q++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
// Horizontal symmetry (the upper and the lower rows)
for (int i = 0; i <= c - a; i++) {
for (int j = b; j <= d; j++) {
dsu.unite(
id(a + i, j),
id(c - i, j)
);
}
}
// Vertical symmetry (the left and the right columns)
for (int i = a; i <= c; i++) {
for (int j = 0; j <= d - b; j++) {
dsu.unite(
id(i, b + j),
id(i, d - j)
);
}
}
}
// Counting the different DSU components
vector<char> seen(total, 0);
int components = 0;
for (int i = 0; i < total; i++) {
int root = dsu.find(i);
if (!seen[root]) {
seen[root] = 1;
components++;
}
}
// Calculating 2^components mod MOD
long long result = 1;
long long base = 2;
int exp = components;
while (exp > 0) {
if (exp & 1) result = (result * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
cout << result << "\n";
return 0;
}
Task 6 – Labelling
Time limit: 0.1s Memory limit: 64MB
Input: stdin Output: stdout
Task
Miki has prepared N jars and wants to label them. He has K labels available, numbered from 1 to K. The labelling process goes like this:
- Miki chooses the first place
idx₁(1 ≤ idx₁ ≤ N) and puts the label number 1 there. -
For every next label
t = 2..Ka new placeidx_tis chosen so that|idx_t − idx_{t−1}| = 1. The labeltis put at that place, replacing the existing one if there is one.
Denis proposes a final configuration of labels
e₁, e₂, …, e_N (jars without a label are marked with 0).
You need to calculate how many different processes can lead to that configuration.
Give the result modulo 998244353.
The input contains N and K in the first line and the numbers e₁ … e_N in the second line. For example, for N = 3, K = 3 and the configuration 2 3 0 the answer is 1 (the only process is: label 1 on jar 2, label 2 on jar 1, label 3 on jar 2).
Hint — the idea of the solution
The key observation
- Every label
tis put exactly once, in the stept, at the positionidx_t. - The final label at the position
jis the largest numbertfor which that position was visited. - If the final array contains
e_j = t, then the label t must have been put exactly at that position. - If the label
tdoes not appear in the arraye, it could have been put at any position wheree_j ≥ t(because it will later be overwritten by a larger label). - The movement is always local: in every step we move exactly one place left or right.
- If some
e_jis greater thanK, that label was never put, so the answer is 0.
Dynamic programming
- We define
dp[t][j]= the number of ways to be at the positionjafter putting the labelt. - The allowed positions in the step
tare alljfor whiche_j ≥ t. - If there is a position
jwithe_j = t, thenidx_tis fixed and only that position is allowed.
The transition
dp[t][j] = dp[t−1][j−1] + dp[t−1][j+1]
(of course, only if the position j is allowed in the step t).
The base case
- For
t = 1we can start from any position wheree_j ≥ 1. - So
dp[1][j] = 1for all such positions.
The final answer
- After the step
K, we add up alldp[K][j]wheree_j ≥ K.
Solution (C++)
// Task 6 – Labelling
// Dynamic programming over time (labels) and position
#include <bits/stdc++.h>
using namespace std;
static const int MOD = 998244353;
inline int addmod(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
cin >> N >> K;
// e[i] = the final label at the position i (1-indexed)
vector<int> e(N + 2, 0);
for (int i = 1; i <= N; i++) {
cin >> e[i];
if (e[i] > K) { // the label e[i] was never put
cout << 0 << "\n";
return 0;
}
}
// dp_prev[j] = dp[t-1][j], dp_cur[j] = dp[t][j]
vector<int> dp_prev(N + 2, 0), dp_cur(N + 2, 0);
// t = 1 (the base case)
bool possible = false;
for (int j = 1; j <= N; j++) {
if (e[j] >= 1) {
dp_prev[j] = 1;
possible = true;
}
}
if (!possible) {
cout << 0 << "\n";
return 0;
}
// DP over the labels 2..K
for (int t = 2; t <= K; t++) {
fill(dp_cur.begin(), dp_cur.end(), 0);
int forced_pos = -1;
for (int j = 1; j <= N; j++) {
if (e[j] == t) {
forced_pos = j;
break;
}
}
if (forced_pos != -1) {
int j = forced_pos;
int ways = 0;
if (j > 1) ways = addmod(ways, dp_prev[j - 1]);
if (j < N) ways = addmod(ways, dp_prev[j + 1]);
dp_cur[j] = ways;
} else {
for (int j = 1; j <= N; j++) {
if (e[j] >= t) {
int ways = 0;
if (j > 1) ways = addmod(ways, dp_prev[j - 1]);
if (j < N) ways = addmod(ways, dp_prev[j + 1]);
dp_cur[j] = ways;
}
}
}
dp_prev.swap(dp_cur);
}
long long answer = 0;
for (int j = 1; j <= N; j++) {
if (e[j] >= K) {
answer = (answer + dp_prev[j]) % MOD;
}
}
cout << answer << "\n";
return 0;
}
