# SCRRCP - Editorial

Setter: Farhan Hasin
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

Easy-Medium

# PREREQUISITES:

Bitwise Operations, Greedy, and Observation

# PROBLEM:

There exist a hidden array A of length N where N is known, all elements of the array A are distinct and we are allowed to ask the following query at most K = 5000 times, to recover the array A.

• For some x we choose, the judge returns the value v with a minimum value of x \oplus v (which is guaranteed to be unique).

# QUICK EXPLANATION

• The smallest value in the array can be found by querying 0 which would return the minimum value in the array.
• Now, assuming we have found the smallest i values, largest among them being x, we can find the next greater value as follows:
• Iterate over bits b from least significant to most significant.
• Set all bits lesser significant than b-th bit to 0, set b-th bit to 1 and rest bits the same as x. Say we got y
• Querying y would give either x or the next greater element.

# EXPLANATION

First of all, it is easy to see that when queried 0, we would get the minimum element in the array, since x \oplus 0 is x.

Now, we’d be obtaining the array in increasing order of values. Let’s assume we have found first i values from the array, the largest one being X.

Let’s assume the smallest value not yet found is Y.

Writing X and Y in binary form, if first b bits are the same, we can prove that for every Z \geq Y, the number of bits in common between X and Z would be less than or equal to b.

Proof

Let’s assume there exists Z with first b+1 bits common same as X and X < Y < Z.

Now, At (b+1)-th bit, Both X and Z have this bit not set while Y has this bit set. But this implies Y > Z, which contradicts with X < Y < Z

Hence, there cannot exist any Z > Y with more than first b bits in common with X

Now, let’s try to find this value of b. Notice that if we have a number Z with first b+1 bits same as Y, X \oplus Z > Y \oplus Z since X \oplus Z will have (b+1)-th bit set while Y \oplus Z will have first (b+1) bits off. Hence, setting remaining bits to 0, we’d get the minimum value greater than Z which is Y.

We can actually query for each possible b from least significant to most significant and query Z, we can find next value within B queries where B is the number of bits.

Hence, the total number of queries is N*B in the worst case. Considering N = 85 and B = 60, N*B = 5100 which is outside the limit, but we found minimum using one query and can similarly find maximum using one query, so the resulting number of queries become 4982.

Can you prove any stricter query limit?

# TIME COMPLEXITY

The time complexity is O(N*B) per test case,

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
#define BIT 60

using namespace std;
typedef long long ll;

int n;
set<ll>v;
int node;
int idCnt;

void init(int id)
{ /// creating new node
node[id]=-1;
node[id]=-1;
}

void insert(ll x)
{
int cur=0;
for(int i=BIT-1;i>=0;i--)    {
bool val=x&(1LL<<i);
if(node[cur][val]==-1){
init(++idCnt);
node[cur][val]=idCnt;
}
cur=node[cur][val];
}
}

void query(ll x) {
cout<<1<<" "<<x<<endl;
ll y;cin>>y;
v.insert(y);
insert(y);
}

void dfs(int nd,int dep,ll prefix) {
if(nd==-1 || dep==0 || v.size()==n) return;

if(node[nd]==-1) {
query(prefix);
}

if(node[nd]==-1) {
query(prefix|((1LL<<dep)-1));
}

dfs(node[nd],dep-1,prefix);
dfs(node[nd],dep-1,prefix|(1LL<<(dep-1)));
}

int main() {

int t;
cin>>t;

while(t--) {

cin>>n;
v.clear();
memset(node,0,sizeof(node));
idCnt=0;

init(0);
dfs(0,BIT,0);

cout<<2<<" ";

int it=0;
for(auto x:v) {
cout<<x;
if(it!=n-1) cout<<" ";
else cout<<endl;
it++;
}
cin>>it;
if(it==-1) break;

}

return 0;
}
``````
Tester's Solution
``````//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
#define int ll

vi vec;
int cnt=0;
int query(int val){
cnt++;
cout<<1<<" "<<val<<endl;
fflush(stdout);
int y;
cin>>y;
return y;
// vi gg;
// gg.clear();
// gg.pb(2);
// gg.pb(3);
// gg.pb(7);
// gg.pb(10);
// int x=gg,i;
// //cin>>x;
// rep(i,gg.size()){
// 	if((gg[i]^val)<(x^val)){
// 		x=gg[i];
// 	}
// }
//return x;
}
int solve(int sofar,int curbit,int curmin){
if(curbit==-1){
vec.pb(sofar);
return 0;
}
if(curmin&(1LL<<curbit)){
solve(sofar+(1LL<<curbit),curbit-1,curmin);
return 0;
}
int val=sofar+(1LL<<curbit);
int ans=query(val);

if(ans&(1LL<<curbit)){
solve(val,curbit-1,ans);
}
solve(sofar,curbit-1,curmin);
return 0;
}
signed main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
cnt=0;
int n;
cin>>n;
vec.clear();
int val=(1LL<<59);
int ans=query(0);
if(ans&val){
solve(val,58,ans);
}
else{
solve(0,58,ans);
ans=query(val);
if(ans&val){
solve(val,58,ans);
}
}
cout<<2<<" ";
int i;
sort(all(vec));
assert(vec.size()==n);
rep(i,vec.size()){
cout<<vec[i]<<" ";
}
cout<<endl;
fflush(stdout);
cin>>i;
cerr<<cnt<<endl;
}
}
``````
Editorialist's Solution
``````import java.util.*;
import java.io.*;
import java.text.*;
class SCRRCP{
//SOLUTION BEGIN
int B = 60;
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();cnt = 0;
long[] a = new long[n];
a = query(0);
for(int i = 1; i< n; i++){
long cur = a[i-1];
for(int b = 0; b< B; b++){
long nxt = cur^(1L<<b);
if(nxt > cur){
long val = query(nxt);
if(val > a[i-1]){
a[i] = val;
break;
}
}else cur = nxt;
}
}
StringBuilder ans = new StringBuilder("2");
for(long l:a)ans.append(" "+l);
pni(ans.toString());
hold(ni() == 1);
}
int cnt = 0, Q = 5000;
long query(long x) throws Exception{
hold(++cnt <= Q);
pni("1 "+x);
return nl();
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new SCRRCP().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
``````

Feel free to share your approach. Suggestions are welcomed as always. 1 Like

Can you explain where my this submission is failing that is I am getting persistent Wrong answers.

Is there a tight bound of randomization error for this problem? My solution that simply queried 5000 random numbers passed first try (https://www.codechef.com/viewsolution/30903596).

3 Likes

You are using (1<<j), it will not work for j>30.

ok

why this solution is correct?what your query function actually does?
why you sort the sequence?

The solution’s correct because the test cases are bad – there’s actually a case that makes my solution have a 2^-60 chance of succeeding per query (0, 1, 2, 4, 8, …, 2^59, which requires the solution to query 0 to find it).

The query function outputs a number, and reads in the answer. It then checks the answer against the numbers I already have with the set, and if it’s unique, it gets added into the set and onto the sequence.

I sort the sequence because the problem requires the output to be sorted.

1 Like

why the answer is always first n numbers of seq ?

The problem guarantees that each number in the hidden sequence is unique (otherwise it wouldn’t be possible). I only append to `seq` when I encounter a new number, which I check for by using the set. Thus, `seq` will contain each number in the hidden sequence exactly once, provided I find them all. The first n elements are the only n elements.

1 Like

https://www.codechef.com/viewsolution/30969622
I did exactly what was given in the editorial and Im getting WA.