PROBLEM LINK
Setter : ki0apa
Tester : Rahul Dugar
Editorialist : Rajarshi Basu
PREREQUISITES
Observation Skills
DIFFICULTY
Medium
PROBLEM
This is an interactive problem.
Joshua is hiding a sequence A_1, A_2, \ldots, A_N, where N is even. He wants to play a game with you. Your goal is to guess the sequence.
First, Joshua tells you A_1 and A_N. Then, you should ask him queries. In each query, you choose four integers L_1, R_1, L_2 and R_2 such that 1 \le L_1 \lt R_1 \le N and 1 \le L_2 \lt R_2 \le N, and Joshua’s answer is the maximum of A_{L_1}, A_{L_1+1}, \ldots, A_{R_1} minus the minimum of A_{L_2}, A_{L_2+1}, \ldots, A_{R_2}.
Can you find the sequence using no more than 2N queries?
Constraints
- 2 \le N \le 10^5
- N is even
- 1 \le A_i \le 10^9 for each valid i
BRIEF EXPLANATION
quick quick
We always use length 2 queries. In particular, let us already know A_i. Then query
- x = max(A_i, A_{i+1}) - min(A_{i+1} , A_{i+2})
- y = max(A_{i+1} , A_{i+2}) - min(A_i, A_{i+1})
Then A_{i+2} = A_i - (x-y). Continuing this, we will get the value of all odd indices if we start from first, and all the values of the even indices if starting from back. [Note that n is even.
EXPLANATION
First Observations
It should strike immediately that making queries on big ranges dont really give us more information than querying on short ranges. Rather, it, in some sense, “dilutes” the information. This should make you try to query short ranges, especially ranges of size 2, since that in some sense gives you the most information.
How to make such queries
The next part is what queries to make. This is a bit harder to derive and more of a hit and guess. The main intuition should be trying to make the two ranges either completely overlap or atleast partially.
Solution 1 - Is this correct?
The following solution is easy and quick to come up with. Make both the ranges the same, and do it for every two consecutive elements. I:e, Make queries like max(A_i, A_{i+1}) - min(A_i, A_{i+1}) for every i. This should give you the difference between every two consecutive elements, but without the sign. Now, make queries like max(A_i, A_{i+1}, A_{i+2}) - min(A_i, A_{i+1}, A_{i+2}). Now if this difference is the same as the difference between the two pairs of consecutive elements, then it means both of these difference have same sign, or otherwise different. This essentially fixes the signs of all the differences, if we fix the sign of atleast one of the differences. Here also, the number of queries is \leq 2N. But the thing is, is this correct? How do we determine the sign of atleast one of the consecutive differences?
countercase
The obvious idea should be, choose either sign for the first difference. However, that might not be enough. Consider the following testcase: A = \{ 0,2,-2,0 \}. How do you distinguish between this and A = \{0,-2,2,0\}.
CHALLENGE : Can you make this work? Remember, we still have leftover queries, maybe use that?
Final Solution
Since complete overlap may or may not work (solve the Challenge!!), lets try partial overlap. Consider the following queries :
- x = max(A_i, A_{i+1}) - min(A_{i+1} , A_{i+2})
- y = max(A_{i+1} , A_{i+2}) - min(A_i, A_{i+1})
Now convince yourself (some easy casework) that A_{i+2} = A_i - x + y in all cases. However it is not possible to get the value of A_{i+1} from here… but we don’t need to. If we start from A_1, we can get all the values A_1 \rightarrow A_3 \rightarrow A_5 \rightarrow … A_{n-1}. Similarly if we start from A_n and go backwards, we can get A_n \rightarrow A_{n-2} \rightarrow A_{n-4} \rightarrow ... \rightarrow A_2. Hence, overall, all the indices will be covered.
SOLUTION
Tester’s Code
#pragma GCC optimize("Ofast")
#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<int, null_type, less<int>, 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,' ');
}
int a[100005];
int aa[100005]={0,1,2,3,1};
int nq=0;
vector<pair<pair<pii,pii>,int>> qurs;
map<vi,int> cache;
int query(int l1, int r1, int l2, int r2) {
if(cache.find({l1,r1,l2,r2})!=cache.end())
return cache[{l1,r1,l2,r2}];
// int pp=(*max_element(aa+l1,aa+r1+1))-(*min_element(aa+l2,aa+r2+1));
// nq++;
cout<<"Q "<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<endl;
int pp=readIntLn(-1000000000,1000000000);
cache[{l1,r1,l2,r2}]=pp;
qurs.pb({{{l1,r1},{l2,r2}},pp});
return pp;
}
int difs[100005];
int n;
void solve() {
// int n=100;
// a[1]=aa[1];
// a[n]=aa[n];
int n=readIntSp(1,100000);
a[1]=readIntSp(1,1000000000);
a[n]=readIntLn(1,1000000000);
if(n==2) {
cout<<"! "<<a[1]<<" "<<a[2]<<endl;
return;
}
assert(n%2==0);
rep(i,1,n)
difs[i]=query(i,i+1,i,i+1);
int i=1;
while(i+2<=n&&difs[i]==difs[i+1]) {
if(query(i,i+2,i,i+2)==difs[i])
a[i+2]=a[i];
else
break;
i+=2;
}
if(i!=n-1) {
vi cands={a[i]+difs[i],a[i]-difs[i]};
if(query(i,i+2,i,i+1)>query(i,i+1,i,i+1)) {
// a[i+2]>max(a[i],a[i+1])
if(query(i,i+1,i,i+1)>query(i,i+1,i+1,i+2)) {
// a[i]<a[i+1]
a[i+1]=cands[0];
} else
a[i+1]=cands[1];
} else if(query(i,i+1,i,i+2)>query(i,i+1,i,i+1)) {
// a[i+2]<min(a[i],a[i+1])
if(query(i,i+1,i,i+1)>query(i+1,i+2,i,i+1)) {
a[i+1]=cands[1];
} else
a[i+1]=cands[0];
} else {
// min(a[i],a[i+1])<a[i+2]<max(a[i],a[i+1])
if(query(i,i+1,i,i+1)==query(i+1,i+2,i,i+1)) {
a[i+1]=cands[0];
} else
a[i+1]=cands[1];
}
}
int known=i;
rep(i,2,n) {
if(a[i])
continue;
if(query(known,known+1,i-1,i)>max(a[known],a[known+1])-a[i-1]) {
a[i]=a[i-1]-difs[i-1];
} else
a[i]=a[i-1]+difs[i-1];
}
cout<<"!";
fr(i,1,n)
cout<<" "<<a[i];
cout<<endl;
// trace(nq);
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(7);
// int t=readIntLn(1,1000);
int t=1;
fr(i,1,t)
solve();
assert(getchar()==EOF);
#ifdef rd
// cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}