FINXOR - Editorial

editorial
, , , , , ,
9

Interesting, I didn’t use matrices at all or have to use gaussian elimination. Will post an explanation later but here is the code.

def ask_questions(n):
    print("1 1")
    k_zero = int(input())
    if k_zero == -1:
        raise Exception("cant ask with k == zero")
    last_digit = (n - k_zero) % 2
    reverse_digits = [last_digit]
    n_digits = 20
    for digit in range(1, n_digits):
        # ask question
        print(f"1 {((1<<n_digits)-1) - (1<<digit)  - 1}")
        # get the answer
        ans = int(input())
        x = k_zero + ans
        double_number_ones = x - n * (
            ((((1 << n_digits) - 1) ^ (1 << digit)))
        )
        reverse_digits.append(((double_number_ones >> (digit + 1))) & 1)
    ans = sum(reverse_digits[i] << i for i in range(len(reverse_digits)))
    print(f"2 {ans}")
    is_correct = int(input())
    if is_correct != 1:
        raise Exception("incorrect")


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        N = int(input())
        ask_questions(N)
10

There is no. need of any matrix …it is just simple logic…i dont know why they used gaussian elemination like stuff…here is my code simple logic.Please explain the editorial in the most simplest way so that the users can understand and not fear the editorial

    #include <bits/stdc++.h>
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    #define whatis(x) cout << #x << " is " << x << endl;

    //initialization of variable
    int numone[20];
    ull totalsum;
    ull xorsum[20];
    int n;

    void solve() {
        for (int i = 0; i < 20; i++) {
            ull k = (1 << i);
            ull tempsum = (totalsum + xorsum[i]);
            tempsum = tempsum - (n * k);
            tempsum = tempsum / 2;
            ull currentbitsum = totalsum - tempsum;
            currentbitsum = currentbitsum / k;
            numone[i] = currentbitsum;
        }
    }

    //Initializer function
    void init() {
        memset(numone, 0, sizeof(numone));
        memset(xorsum, 0, sizeof(xorsum));
        totalsum = 0;
        n = 0;
    }

    //Query function
    void query() {
        ull q = (1 << 20);
        cout << 1 << " " << q << endl;
        cin >> totalsum;
        totalsum = totalsum - (ull)(n*q);
        for (int i = 1; i < 20; i++) {
            q = (1 << i);
            cout << 1 << " " << q << endl;
            cin >> xorsum[i];
            if (xorsum[i] == (-1)) {
                exit(0);
            }
            cout.flush();
        }
    }`Preformatted text`

    //Function to print the ans
    void ans() {
        ull ans = 0;
        for (int i = 19; i > 0; i--) {
            if (numone[i] % 2 != 0) {
                ans = ans + (ull)(1 << i);
            }
        }
        totalsum = totalsum - ans;
        if(totalsum%2!=0){
            ans+=1;
        }
        cout << 2 << " " << ans << endl;
        cout.flush();
        int res;
        cin >> res;
        if (res == (-1)) {
            exit(0);
        }
    }
    int main() {
        ll test;
        cin >> test;
        while (test--) {
            init();

            cin >> n;
            //Initialization

            //Query for all the bits
            query();

            //Solve for the number of bits
            solve();

            //ans the sum
            ans();
        }
    }
7 Likes
11

yes used the same logic,observations can really simplify the solution

1 Like
12

yes…no need of any equation like stuff

2 Likes
13

Here’s another approach, i didn’t used matrix…

https://www.codechef.com/viewsolution/37690291

14

Actually, there’s one simple approach. Because of constraints of K, you can ask 20th power of 2 which is greater than 10^6 and less than 2* 10^6. and asking 2^20 will give you sum of all elements in the array.

After knowing the sum of all the elements of the array, now if you ask a question(only particular bit), lets say 64(2^6), then you can figure out the difference in value which is given by grader and the total sum and can find a pattern :slight_smile: .

link to my solution : CodeChef: Practical coding for everyone

4 Likes
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 ?