FINXOR - Editorial

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 ?

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

Yes, I’ve used the same logic.

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

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.

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

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

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 == n
k)
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;
}
}

can you briefly explain what you have done ?

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…

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

1 Like

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.

@krikti i have solved , assuming that k<=10^6 then the code would slightly change…
here is my solution->https://www.codechef.com/viewsolution/37924226

@wm101
Your Explaination was great!
Can you please tell that How you computed the generalised inverse of the matrix?

Yes, the logic remains same.

But to do Gaussian Elimination in C / C++ is bit hard. On the other hand, there are in-built functions for the same in Python.

1 Like

Yes its hard to implement in C++.
@krikti
Can you please explain how @wm101 computed the generalised inverse of the matrix (of order >=3)?

Tough part was computing inverse in this problem.
Can You Please Explain?

does not make this question look more tough by doing gaussian- elimination

I personally tried finding inverses, and noticed a pattern, which I then proved using a direct calculation.

Okay Thanks!

can anyone help me to figure out mistake in my solution

link to my solution:
https://www.codechef.com/viewsolution/37705280