PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Farhan Hasin
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
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[20005][2];
int idCnt;
void init(int id)
{ /// creating new node
node[id][0]=-1;
node[id][1]=-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][0]==-1) {
query(prefix);
}
if(node[nd][1]==-1) {
query(prefix|((1LL<<dep)-1));
}
dfs(node[nd][0],dep-1,prefix);
dfs(node[nd][1],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[0],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[0] = 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;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
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());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 