PROBLEM LINK:
Setter: Shahjalal Shohag
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu
DIFFICULTY:
Medium
PREREQUISITES:
Binary Search and Interactive-Problem
PROBLEM:
There is a hidden sequence of integers A_1, A_2, ..., A_N, and you have to find out this sequence by asking queries. You may ask up to 2,222 queries. In each query :
- You should choose two integers K and X (1≤K≤N+1, 1≤X≤10^6).
- A new sequence B_1, B_2,…,B_{N+1} is created, where B_K=X and if we deleted the element B_K from this sequence, we would obtain the sequence A.
- And the interactor will return the number of inversions in the sequence B.
QUICK EXPLANATION:
- We represent query as, query(K, X), where K is the position in the sequence B, and X is B_K.
- Inversions in sequence A = query(1, 1). let it be inv
- Initially, the whole sequence A is unknown. We can find the sequence A by repeatedly finding the smallest unknown element by using binary search over the range [1, 10^6] to find the smallest integer X such that query(1, X) > inv, let the smallest X be X', So this means there are some position/positions in the sequence A where integer X'-1 present.
- We can now find position/positions of the integer X'-1 by applying binary search over the range [1, N].
- Assign inv = query(1, X')
- We will repeat the above process till we don’t find any new elements, and if there are still some positions unknown in the sequence A after finishing the above process, then it means at that location/locations A_i = 10^6.
- Finally you can reduce the count of queries asked by storing the result of queries and preventing asking the same queries again and again.
EXPLANATION:
For simplicity, we represent query as, query(K, X), where K is the position in the sequence B, and X is B_K.
Initially, the whole sequence A is unknown. Now how can we progress further? We will find the smallest unknown integer yet to found in the sequence A and then we will find the position/positions where this integer is present in the sequence A, we will update those positions and then we will find the next smallest unknown integer and in this way, we will find the whole sequence A. Now how to do this efficiently.
Now If I ask query(1,1) then the count of inversions remains the same. So by this query, I get the total number of inversions in the sequence A. Let us store the number of inversions in the variable named inv. Now let us use binary search over the range [1, 10^6] to find the smallest element, How will we know it? Suppose if we ask query(1, X) and if the inversions returned by it is greater than the count of inversion stored in variable inv, this means that there are some elements present in the sequence A which is less than X. So we will apply binary search to find out the smallest X such that query(1, X) > inv, let the smallest X be X', So this means X'-1 is present in some position/positions of the sequence A(as it introduced the extra inversions). Also store query(1, X') in variable newinv (will be used later).
Ok, finding the smallest unknown element is done, now we have to find its position/positions in the sequence A. Now the number of extra inversions introduced will be equal to the frequency of X'-1 in the sequence A and it will be equal to newinv - inv, let the frequency be y. Now you have to apply y binary searches to find all its positions. How to find the first position? For this, you have to apply binary search on the range [1, N] and ask query query(position, X'-1), Now let’s think about how to modify this query to indicate the location/locations of the integer X'-1.
- When we ask query(pos, X'-1), an integer X'-1 is inserted in sequence A at position pos. Let the value of query(pos, X'-1) be curinv, and it represent the inversion count in sequence B.
- Some positions might be known and some will still be unknown (initially all positions are unknown).
- Let us represent known positions by * and unknown positions by -1.
- So B will be in the following form:
{*, -1, -1, *, *, X'-1, *, -1, -1, *, -1, -1, -1, -1, X'-1, -1, *}
^ ^
| |
(Already Found) (Inserted Element)
- curinv = inversion in A + inversions introduced by the Inserted Element.
- So we subtract the inversion count of A from curinv, then we will get the inversion count introduced by the inserted element.
- Now from this count if we reduce the count of known elements smaller in the right of the asked position (which will introduce inversion as they are smaller and all the unknown elements are either equal or greater so they will not introduce any inversions).
- Now for the left side if we reduce the count of the unknown elements which will be either greater or equal to X'-1. Then there will be two cases
- Resultant curinv becomes negative, it means that there are some X'-1 integers to the left of pos which are unknown (as they don’t introduce inversion but we are still reducing from curinv. So we go to the left side and in this way, we will find the first unknown position of X'-1 using binary search.
- Resultant curinv becomes 0, it means that all the unknown to the left side of pos is greater than X'-1 and hence we will go to the right side.
int freq = newinv-inv;
for(int i = 1; i <= freq; i ++) {
int L = 1, R = N, mid, pos = -1;
while(L <= R) {
mid = (L+R)/2;
int curinv = query(mid, X-1);
curinv -= inv_in_A;
for(int i = 1; i < mid; i ++) {
if(A[i] == -1) curinv --;
}
for(int i = mid; i <= N; i ++) {
if((A[i] != -1) && (A[i] < X-1)) curinv --;
}
if(curinv == 0) {
pos = mid;
L = mid+1;
}
else R = mid-1;
}
A[pos] = X-1;
}
- And in this way we will apply binary search to find the location/locations. Note we have to find y locations.
Ok, now we have found the smallest integer in the sequence A and all its positions in the sequence. Now to find the next smallest integer first update inv to newinv(I will tell you why) we have to find the smallest integer X such that query(1, X) is greater than the inv (or newinv) as this will introduce the extra inversion from the smallest element and the next smallest element, so to find the next smallest element we have to update inv to newinv and again repeat the above process. Now we will terminate the above process when we can’t find an integer in the range [1, 10^6] which will introduce extra inversion.
Now one more thing to note is that integer 10^6(if present in the sequence A) will not introduce extra inversion as it is the highest number for which we can ask the query, so all the position in the sequence A which is not found after applying the above process implies that at these positions integer 10^6 is present, so you can simply assign this value.
Now you will note one thing even applying the above process you are exceeding the query limit (in the worst case you will ask [100*log(10^6)+100*log(10^2)] i.e. nearly 2700 queries). So how to optimize it? You can optimize it by storing the result of the queries in a map and when you again have the same query, you can simply return the result stored in the map instead of asking the query again, and by this, you will greatly reduce the count of queries. (Note: for this optimization, you have to always start with the initial range i.e. [1, 10^6])
Proof for the optimization
Consider a complete binary search tree in which the root represents the range [1, 10^6], its left child represents the range [1, 5*10^5] and right child represents the range [5*10^5 + 1, 10^6] and so on dividing the ranges into two halves. Now when we try to find the smallest integer X by querying, we are basically querying over the mid of the range of the node of the binary search tree and depending on the result we are going to the left or to the right child reducing the search range. Now if we store the result of the queries for mid of the first 6 layers of the nodes of the binary search tree that is 2^7 - 1 = 127 nodes then the range length will reduce to nearly 10^4. so we can find the sequence A in 127 + 100*log(10^4) + 100*log(10^2) queries which is nearly equal to 2227 queries but as N \leq 100, in the worst case, the number will be nearly equal to 2140 queries. Note that you don’t have to ask queries separately for the mid of 127 nodes, just store all the queries you ask in a map while following the above process to avoid asking the same query again.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int N = 109, M = 1e6;
map<int, int> mp[N];
int ask(int k, int x) {
if (mp[k].find(x) != mp[k].end()) {
return mp[k][x];
}
cout << "? " << k << ' ' << x << '\n';
cout.flush();
int inv; cin >> inv;
return mp[k][x] = inv;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> ans(n + 1, 0);
int tot = ask(1, 1);
int last = tot;
while (1) {
int l = 1, r = M, cur = M, inv;
while (l <= r) {
int mid = l + r >> 1;
int nw = ask(1, mid);
if (nw > last) {
cur = mid - 1;
r = mid - 1;
inv = nw;
}
else {
l = mid + 1;
}
}
if (cur == M) {
for (int i = 1; i <= n; i++) {
if (ans[i] == 0) {
ans[i] = M;
}
}
break;
}
else {
int c = inv - last;
assert(c > 0);
while (c--) {
int l = 1, r = n, id = -1;
while (l <= r) {
int mid = l + r >> 1;
int nw = ask(mid, cur);
nw -= tot;
for (int i = 1; i < mid; i++) {
nw -= ans[i] == 0;
}
for (int i = mid; i <= n; i++) {
nw -= ans[i] != 0 && ans[i] < cur;
}
if (nw == 0) {
id = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
assert(id != -1);
ans[id] = cur;
}
}
last = inv;
}
cout << "! ";
for (int i = 1; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
cout.flush();
for (int i = 0; i < N; i++) {
mp[i].clear();
}
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
//#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
vi dist;
int normie=0;
int n;
int query(int p, int val) {
cout<<"? "<<p<<" "<<val<<endl;
int te=readIntLn(0,(n*(n+1LL))/2);
// cin>>te;
te-=normie;
return te;
}
void go(int lb, int lo, int hi, int cnt) {
// trace(lb,lo,hi,cnt);
if(cnt==0)
return;
if(lo==hi) {
fr(i,1,cnt)
dist.pb(lo);
return;
}
int mid=(lo+hi+1)/2;
int pp=query(1,mid)-lb;
go(lb,lo,mid-1,pp);
go(lb+pp,mid,hi,cnt-pp);
}
void solve() {
n=readIntLn(1,100);
// cin>>n;
dist.clear();
normie=0;
normie=query(1,1);
go(0,1,1000000,n);
// dist={1,2};
// trace(dist);
oset pool;
int cntr=0;
vi anser;
vector<pii> polol={{0,0}};
for(int i:dist)
if(i==polol.back().fi)
polol.back().se++;
else
polol.pb({i,polol.back().se+1});
fr(i,1,n) {
int lo=1,hi=sz(polol)-1,mid=(lo+hi)/2;
while(lo<hi) {
int pp=query(i+1,polol[mid].fi)-sz(pool)+pool.order_of_key({polol[mid].fi+1,0});
int chota=polol[mid-1].se-pool.order_of_key({polol[mid].fi,0});
// trace(pp,chota,lo,mid,hi,i);
if(chota>=pp) {
hi=mid;
} else
lo=mid+1;
mid=(lo+hi)/2;
}
pool.insert({polol[mid].fi,++cntr});
anser.pb(polol[mid].fi);
}
cout<<"!";
for(int i:anser)
cout<<" "<<i;
cout<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);
int t=1;
// cin>>t;
t=readIntLn(1,20);
fr(i,1,t) {
solve();
}
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
map<int, int> q[105];
int query(int K, int X) {
if(q[K].count(X)) return q[K][X];
cout << "? " << K << ' ' << X << endl;
int newinv;
cin >> newinv;
q[K][X] = newinv;
return newinv;
}
void Solve() {
for(int i = 0; i < 105; i ++) {
q[i].clear();
}
int N;
cin >> N;
int inv = query(1, 1);
int inv_in_A = inv;
vector<int> A(N+1, -1);
while(true) {
int L = 1, R = 1e6, mid, X = 1e6, newinv;
while(L <= R) {
mid = (L+R)/2;
int res = query(1, mid);
if(res > inv) {
X = mid;
R = mid-1;
newinv = res;
}
else L = mid+1;
}
if(X == 1e6) {
for(int i = 1; i <= N; i ++) {
if(A[i] == -1) A[i] = 1e6;
}
break;
}
int freq = newinv-inv;
for(int i = 1; i <= freq; i ++) {
int L = 1, R = N, mid, pos = -1;
while(L <= R) {
mid = (L+R)/2;
int res = query(mid, X-1);
res -= inv_in_A;
for(int i = 1; i < mid; i ++) {
if(A[i] == -1) res --;
}
for(int i = mid; i <= N; i ++) {
if((A[i] != -1) && (A[i] < X-1)) res --;
}
if(res == 0) {
pos = mid;
L = mid+1;
}
else R = mid-1;
}
A[pos] = X-1;
}
inv = newinv;
}
cout << "! ";
for(int i = 1; i <= N; i ++) {
cout << A[i] << " ";
}
cout << endl;
}
int main() {
int test_case;
cin >> test_case;
for(int i = 1; i <= test_case; i ++) {
Solve();
}
}
VIDEO EDITORIAL:
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile