PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Anshu Garg
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Binary search
PROBLEM:
There is a hidden array A of size N. You need to find an array B which is equivalent to A, where B is considered equivalent to A if A_i = A_j \iff B_i = B_j for every 1\leq i, j\leq N.
To do this, you can ask upto 6N queries, where each query is as follows:
Provide any subset \{i_1, i_2, \dots, i_k\} of \{1, 2, \dots, N\} to the judge, which then returns the frequency of the mode of the multiset \{A_{i_1}, A_{i_2}, \dots, A_{i_k}\}.
QUICK EXPLANATION:
Build the array one index at a time. If the first i elements are known, the i+1-th can be found by binary searching on the distinct elements known so far.
EXPLANATION:
Suppose the original array A has d distinct elements. Then, it is possible to create an equivalent array B which only contains 1, 2, \dots, d, which is what we will attempt to do.
Let us analyze the given query operation first.
Playing around with it a bit should lead you to the following observations:
- If you provide a set of any size, and the judge returns 1, all elements of the set are distinct.
- As a special case of the above observation, if you provide a set of size 2, the elements of the set are distinct if and only if the judge returns 1.
We will use this to build a solution.
First, without loss of generality, we can assume that A_1 = 1.
Now let us try to find A_2.
With the information we have, the only reasonable query to ask is \{1, 2\}. If the response to this query is 2, A_2 must be equal to A_1; else it must be different. In case it is different, we can set A_2 = 2 w.l.o.g.
What about A_3?
There are two possibilities here: either A_3 equals one of A_1 or A_2, or it is distinct from them.
One way to check this is to use a similar strategy as we used to find A_2 - querying the set \{1, 3\} tells us whether A_1 = A_3, and querying the set \{1, 2\} tells us whether A_1 = A_2. This is enough information to determine A_3.
The above algorithm generalizes to a full solution, albeit one which uses too many queries.
For each index i, query each of \{1, i\}, \{2, i\}, \dots, \{i-1, i\}. This determines A_i.
Of course, this uses \mathcal{O}(N^2) queries, which is too much.
One minor optimization here is to not repeat queries: if A_x = A_y, there is no need to query for both \{x, i\} and \{y, i\} since the result is going to be the same.
In other words, it is enough to query one index corresponding to each distinct element found so far.
This by itself is not really enough to bring the number of queries down significantly - consider an array where all elements are distinct, for example. Keep the idea in mind though, it will help us later.
Reducing the number of queries
Currently, our solution uses i-1 queries to find A_i. How to do better?
A hint on how to accomplish this comes from the limit on the number of queries (and maybe even the fact that the problem is interactive…). 6 is about \log_2 100, which brings to mind binary search!
What to binary search on?
Looking back at our initial solution, it can be broken into two parts: figuring out whether A_i is a new element, and if it isn’t, figuring out what it is.
Remember the earlier optimization of only asking about one index for each distinct element? That will come into play here to help us.
Suppose we want to find A_i, and there have been k distinct elements found so far. Let I = \{i_1, i_2, \dots, i_k\} be a set of indices corresponding to these k elements.
- To check whether A_i is new, it suffices to ask the query \{i_1, i_2, \dots, i_k, i\}
Why?
Note that, since A_{i_1}, A_{i_2}, \dots, A_{i_k} are all distinct, the result of this query is either 1 or 2. If it is 1, A_i is distinct from all of them and is hence new.
- If A_i does happen to be new, we assign it the value k+1 and insert i into the set of representatives.
- Now consider the case when A_i isn’t new. There will be exactly one x \in \{i_1, i_2, \dots, i_k\} such that A_x = A_i because the indices represent distinct elements.
Finding this x can be done with a simple binary search. Once we know x, we can assign A_i = A_x
Details on the binary search
Split I into two halves - say I_1 and I_2.
Note that x is in one of these halves, but not both.
To check whether x \in I_1, query for I_1 \cup \{i\}. If the result of this query is 1, x \notin I_1. If it is 2, x \in I_1.
This reduces the search space by half, continue applying this process till the search space becomes a single element - that is x.
To make implementation simple, notice that it doesn’t really matter what I_1 and I_2 are chosen to be, as long as they are disjoint halves of I. In particular, we can choose them to be intervals and maintain lo and hi pointers as in a normal binary search.
Analyzing the number of queries
We ask one query for each index 2\leq i\leq N to find out whether A_i is new or not. If it isn’t, we run a binary search to find A_i.
If the array has d distinct elements, the binary search step runs N-d times. In the worst case, each one is over a set of size d, and so will require \lceil \log_2 d\rceil queries.
Thus, the total number of queries is bounded above by N-1 + (N-d)\log_2 d.
It can be verified (for example, by writing a program to compute this over all values of N and d) that this value is much less than 6N no matter what d is. For N = 100, the maximum value across all d comes out to be 514, so the limit on the number of queries is not tight at all.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase
SOLUTIONS:
Tester's Solution
//By TheOneYouWant
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
vector<int> curr;
void ask(int l, int r, int ext){
// curr (l to r), and ext
vector<int> to_ask;
for(int i = l; i <= r; i++){
to_ask.push_back(curr[i]);
}
to_ask.push_back(ext);
cout << "? " << to_ask.size() << " ";
for(int i = 0; i < to_ask.size(); i++){
cout << to_ask[i] << " ";
}
cout << endl;
}
int main(){
fastio;
int tests;
cin >> tests;
while(tests--){
int n, q;
cin >> n >> q;
curr.clear();
curr.push_back(1);
int type[n+1];
for(int i = 0; i <= n; i++) type[i] = 0;
type[1] = 1;
int num = 2;
for(int i = 2; i <= n; i++){
int l = 0, r = (int)curr.size() - 1;
ask(l, r, i);
int ans;
cin >> ans;
if(ans == 1){
type[i] = num;
curr.push_back(i);
num++;
continue;
}
while(l<r){
int mid = (l+r)/2;
ask(l, mid, i);
int ans;
cin >> ans;
if(ans == 1){
l = mid + 1;
}
else{
r = mid;
}
}
type[i] = type[curr[l]];
}
cout << "! ";
for(int i = 1; i <= n; i++){
cout << type[i] << " ";
}
cout << endl;
int is_correct;
cin >> is_correct;
assert(is_correct == 1);
}
return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
using namespace std;
using ll = long long;
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector<int> ans(n); ans[0] = 1;
vector<array<int, 2>> active = {{1, 1}};
auto query = [&] (int L, int R, int x) {
cout << "? " << R-L+2 << ' ';
for (int i = L; i <= R; ++i)
cout << active[i][1] << ' ';
cout << x << endl;
int mode; cin >> mode;
return mode;
};
int id = 2;
for (int i = 1; i < n; ++i) {
if (query(0, size(active) - 1, i+1) == 1) { // First occurrence of a[i]
ans[i] = id++;
active.push_back({ans[i], i+1});
continue;
}
int L = 0, R = size(active) - 1;
while (L < R) {
int mid = (L + R)/2;
if (query(L, mid, i+1) == 1) { // a[i] is not equivalent to anything in [L, mid], so it must be equivalent to something in [mid+1, R]
L = mid+1;
}
else { // a[i] is equivalent to something in [L, mid]
R = mid;
}
}
ans[i] = active[L][0];
}
cout << "! ";
for (auto x : ans)
cout << x << ' ';
cout << endl;
int result; cin >> result;
}
}