FINXOR - Editorial

editorial
, , , , , ,
15

This is the kind of editorial which might scare people. It is very nice and probably, the setter made the question with this approach in mind when a much simpler approach was available.

I used this logic:

First query 2^{20}, and store this sum as a reference point. Also, this tells us the parity of the first (least significant) bit. Notice that under the given constraints, none of the elements of the hidden numbers will have the 20^{th} bit occupied. So, if we subtract n*2^{20} from the input, the sum will be the same as obtained by querying for 0. Let the input for 2^{20} be A.

Now query 2^i \forall i \in [1, 19]. Notice that when you xor any number by 2^i, its i^{th} bit gets flipped.

Say there are n numbers with the i^{th} bit turned on and m numbers with the bit turned of. When you queried 2^{20}, the i^{th} bit contributed 2^i*n to the sum and when you query 2^i, it contributes 2^i * m to the sum while the contribution of the other bits does not change. Let the input for 2^i be B.

A-B = 2^i*(n- m)

Thus, n-m = \dfrac{A-B}{2^i}

Also, the total number of elements in the hidden array are n+m = N.

Then n = \dfrac{N + \dfrac{A-B}{2^i}}{2}

If the parity of set bits is odd, then the bit will be set in the final xor as well, else it will not be set.

Code 
for (int t = 0; t < tc; t++){
		int n;
		cin >> n;
		ll ans1 = 0;
		ll sum;
		cout << 1 << " " << 1048576 << endl;
		cin >> sum;
		sum -= n*1048576;
		if(sum%2) ans1 = 1;
		for(int i = 1; i <= 19; i++){
			cout << 1 << " " << (1 << i) << endl;
			ll sum1;
			cin >> sum1;
			ll diff = sum - sum1;
			diff = diff/(1LL << i);
			ll on = (n + diff)/2;
			if(on%2 == 1) ans1 |= (1 << i);
		}
		cout << 2 << " " << ans1 << endl;
		int j;
		cin >> j;
		assert(j == 1);
	}

In the code, N is denoted n, A by sum, B by sum1 and n by on

27 Likes
16

I’m surprised to see Gaussian eliminations and matrixes and stuff, it’s actually quite simple. The main observation/step is the following:
If we first query some X, and than query Y = (X ^ (1 << b)) (same as X, except on position b), we get:
All positions except b will be same everywhere, so their contribution to both sums will be the same.
So, if we subtract these 2 sums, we find 2^b * (ones(b) - zeroes(b)). On the other hand, ones(b) + zeroes(b) = n, meaning we uniquely find number of 1 bits on position b in numbers (A[i] XOR X). We can choose X so that it has all 0-s in positions 0,…,19.

I omitted a few small details, but here’s my solution - CodeChef: Practical coding for everyone.

1 Like
17

CAN SOMEBODY PLEASE HELP ME OUT WITH THIS. I DON’T UNDERSTAND SO AS TO WHAT IS WRONG IN MY LOGIC.
I WAS WAITING FOR 4 DAYS FOR THE CONTEST TO GET OVER AND I BE ABLE TO DISCUSS THE SOLUTION. GOT ANXIETY LEVEL PRO MAX XD

#i nclude < bits / stdc++.h >
using namespace std;

int main()
{
int t;
cin>>t;
long long int arr[22]={1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
for (int i=1;i<21;i++)
{
arr[i]=2*arr[i-1];
}
for(int z=t;z>0;z–)
{
int n;
cin>>n;
cout<<1<<" “<<arr[20];
int ans;
cin>>ans;
ans=ans-(arr[20]*n);
int func = 0;
if (ans%2!=0)
{
func=func+1;
}
for (int i=0;i<20;i++)
{
int ansu;
ansu=ans+(arr[i]*n);
cout<<1<<” “<<arr[i];
int tans;
cin>>tans;
if (((ansu-tans)/(arr[i]*2))%2 !=0)
{
func=func+arr[i];
}
}
cout<<2<<” "<<func<<endl;
int end;
cin>>end;
}
}

18

Here is my simple solution using python.

import sys
def readArr():
	return [int(x) for x in input().split()]

def ask(what):
	print(1,what,flush=True)
	reply = int(input())
	if reply == -1:
		sys.exit(1)
	return reply

def solve():
	N = int(input())
	k = 2**20 - 1
	sm = (N*k - ask(k)) #o+e=n
	ans = 0
	to_use = 0
	for i in range(19):
		n = 2**i;
		tmp = (ask(n) - sm)
		to_use += tmp
		tmp //= n
		ones = (N - tmp) // 2
		#print("tmp",tmp,"ones",ones)
		ans += n*(ones%2)
		#print("ans now",ans)
	#power 19
	mytmp = ((N*k - sm) - to_use - sm) // (2**19)
	ans += (((N-mytmp) // 2) % 2) * (2**19)

	print(2,ans,flush=True)
	flag = int(input())
	if flag == -1:
		sys.exit(1)

if __name__ == "__main__":
	# T = 1
	T = int(input())
	for t in range(T):
		solve()
1 Like
19

thats what is used there in my code

2 Likes
20

I think It Should be:
Lets, define x_{k} for 0<=k<=19, as the number of elements in array A with kth bit “OFF”.

Because if the 2^i th bit is OFF,then only it will contribute to q_{i}

@krikti
Can You Correct me?

21

No, the statement is correct.

Try to verify this by taking a small example. :slight_smile:

1 Like
22

Nice Approach. :slight_smile:

Even during the contest, I was bit surprised seeing majority candidates using similar approach, which I might have missed.

By the way one quick question, If the limitation on maximum value of K was set as 2^{19}, would that effect the logic ?

23

I have done it for (2^19) + 1. Don’t know for 2^19.
Instead of 2^20 we use 2^0 as reference, which i used during contest.
My Solution

Edit: Allowing query 0 with 2^19 constraint will pass

24

Yes, I’ve used the same logic.

25

I totally agree with you on this and that’s the same logic I’ve used in my code.

26

I think if 0 and 2^20 are both not allowed, then we would have to make a slight modification. We would query 1 first and then check the parity of sum - N. Also, we would have had to use 2^i + 1 everywhere, thus it would only be solvable by this approach for K <= 2^19 + 1, if 0 is not allowed.

27

You have asked 21 Questions?
Also you are not flushing the o/p here:

cout<<1<<" “<<arr[20];

You have to flush output after every output and you used one query above the loop, you had 19 remaining and you used 20 inside the loop. The loop runs 20 times. I don’t know about the logical part of your solution, but these were the few mistakes i could find, I hope it helps!

1 Like
28

@krikti For Solving this Problem through Gauss Elimination , Should we follow this : Click Here ?

29

Getting WA in 2nd subtask.
Someone please help!!!

#include<bits/stdc++.h>
using namespace std;
int main()
{
long long t,n,sum,s,k,i,reply,no,out,tm,tp,extra;
cin>>t;
while(t–)
{
cin>>n;
cout<<“1 1048576”<<endl;
cin>>sum;
sum=sum-n1048576;
k=i=1;
s=0;
while(i<20)
{
cout<<"1 "<<k<<endl;
cin>>reply;
if(reply-sum == nk)
goto skip;
if(reply==-1)
exit(0);
extra=(reply-sum)/k;
if(extra>0)
{
tp=extra+(n-extra)/2;
tm=n-tp;
}
else if(extra==0)
{
tp=tm=n/2;
}
else
{
tm=abs(extra)+(n-abs(extra))/2;
tp=n-tm;
}
if(tm % 2)
s^=k;
skip:;
k*=2;
i++;
}
cout<<"2 "<<s<<endl;
cout.flush();
cin>>out;
}
}

30

can you briefly explain what you have done ?

32

But here in this case there is no way of knowing if the last bit is set on not…
From the bit 1 we can see if it should be set or not…

33

the last bit that is 2^20 th bit will not count as 10^6 has elements till 2^19th bit

1 Like
34

in ur code u r strating with k=1 so the highset bit is 18 upto which the the while loop will run & every time the 19’th bit will be skkiped , so it was obvious to get a WA.

35

@krikti i have solved , assuming that k<=10^6 then the code would slightly change…
here is my solution->CodeChef: Practical coding for everyone