BINXOR dec long challenge video solution(Video Link active)

BINXOR video editorial will be available from 3.30 PM.

video link : BINXOR
Solution link : BINXOR Solution

In this video we are to solve the BINXOR problem from codechef.
The problem requires basic knowledge of

  1. Binomial Coeffitient
  2. Bit manipulation (XOR operation specifically

if you find this video helpful leave a like at codechef article here :
likes on codechef article would make me feel better than the youtube like.

Thank you
CodeNCdode

19 Likes

I wander you have not solved this with your ID in contest then how you made video editorial…

4 Likes

Hey bro, Can u tell how you solved BINADD problem ? I got only 50 pts. I tried but …

just try which carry is longest forwarded :slight_smile:

done it
checkout video here : Addition : Dec long challenge video editorial(video link live Now)

3 Likes

well that is very thoughtful

1 Like

Very nicely explained.
I wonder if posting these video editorials require any special permission.

I also did with somewhat the same logic with a different.I think the minimum number of intersection is no_f 1’s in A+no_f 1’s in B-total string length and maximum is min(nof1’s in a,nof1’s in b)…
this is my code
https://www.codechef.com/viewsolution/28365491
i dont know whats wrong with it.
thanks in advance

I used your logic and coded but still I am getting partially correct answer.Here is my code:
#include
#include
#include
#include
#include
#include <unordered_set>
using namespace std;
const long long int M = 1000000007;
long long int count_setbits(string s)
{
return count(s.begin(),s.end(),‘1’);
}

long long int fact(long long int n);

long long int nCr(long long int n,long long int r)
{
return fact(n) / (fact® * fact(n - r));
}

// Returns factorial of n
long long int fact(long long int n)
{
long long int res = 1;
for (long long int i = 2; i <= n; i++)
res = res * i;
return res;
}
int main()
{
long long int t;
cin >> t;
while (t–)
{
long long int n,max_setbits,min_setbits,intersection_setbits,answer=0;
cin >> n;
string a, b;
cin >> a >> b;

	if ((count_setbits(a) + count_setbits(b) - n) > 0)
		intersection_setbits = count_setbits(a) + count_setbits(b) - n;
	else
		intersection_setbits = 0;
	max_setbits = count_setbits(a) + count_setbits(b) - 2 * intersection_setbits;
	min_setbits = abs(count_setbits(a) - count_setbits(b));
	long long int j = min_setbits;
	while (j <= max_setbits)
	{
		answer += nCr(n, j);
		j += 2;
	}
	cout << (answer%M) << "\n";
}

}

there are 2 problems in your code i can see.
problem 1. you should not calculate fact again and again , it may result in tle.
solution 1. simply use and array f[100001] ,something like this , and precompute it , and from fact(int n) , simply return f[n];

problem 2. nCr is not calulated this way for large numbers.
solution 2. use inverse modulo concept to calculate this.

for reference you can see my code

1 Like

I don’t think so you need special permissions , but yes you should make sure that you upload videos only after the contest is over (I always keep this in mind while uploading videos) , but there are people who upload videos during contest , they should understand what they are doing is wrong and should stop doing this.

2 Likes

Thanks Waqar!

you’re welcome man (but for what ?)

1 Like

Hi guys, I am getting WA when I take modulo inverse with 1000000007, and when I take with 1000000005, it gets accepted? Any reason behind this? Am I missing any concept?
Here is my correct solution: Link1
incorrect solution: Link2

Didn’t check your whole code but mod inverse is number to the power of mod-2. Where do you have this exponent in your solution?

Edit: I think this is your error. In your second solution you changed exponents as well.


you can read this article if you are having problem with modulo inverse.

2 Likes

Thanks! it’s clear now. :slight_smile:

you’re welcome man.

3 Likes

your videos help a lot brother.

you can use n C r+2 = ( (n-r)*(n - r - 1) /( (r + 2) *(r+1) ) *n C r so once calculated for minimum you can calculate it like for two jumps in O(1) space and time.