MYSARA Video Solution

Official editorial coming soon
Video link: MYSARA Solution - CodeChef March Cook-Off 2020 - YouTube
Commented code: CodeChef: Practical coding for everyone

6 Likes

I did almost everything same but in that last calculation part i did
ans = 1 << c;
ans %= MAX;

and i got WA
.
can you please tell me how is this different than your approach?

This number can be very large for long long to hold.

2 Likes

My Solution

I am wondering why your solution is accepted?
since you declare linear vector then it suddenly changes to vector of vectors.
can you explain?

v is the linear vector containing the input, varr is an array of vectors. I think you misread.

okay

okay thanks,
I don’t know how I missed that part. :confused: :see_no_evil:

1 Like

I found two accepted solutions of this question showing different answers

Testcase

1
2
2 4
solution1
solution2

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define lf long double
#define vi vector<int>
#define vl vector<long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define mod 1000000007
#define pb push_back
#define in insert
#define all(x) x.begin(),x.end()
#define zapp ios::sync_with_stdio(false);cin.tie(0)

ll mm(ll a, ll b) 
{ 
    ll res = 0; 
    a %= mod; 
    while (b) 
    { 
        if (b & 1) 
            res = (res + a) % mod; 
        a = (2 * a) % mod; 
        b >>= 1;
    } 
    return res; 
}

int main()
{
	zapp;
	ll t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		ll i,b[n];
		for(i=0;i<n;i++)
		{
			cin>>b[i];
		}
		bool inc = true;
		for(i=1;i<n;i++)
		{
			if(b[i]<b[i-1])
				inc = false;
		}
		if(!inc)
		{
			cout<<0<<"\n";
			continue;
		}
		ll nd[n];
		nd[0] = 1;
		for(i=1;i<n;i++)
		{
			nd[i] = pow(2,__builtin_popcount(b[i] & b[i-1]));
		}
		ll ans = 1;
		for(i=0;i<n;i++)
		{
			ans = mm(ans,nd[i]);
			ans = ans % mod;
		}
		cout<<ans<<"\n";
	}
}

Hi, @tmwilliamlin , first of all i don’t know how question test cases are generating the given output and second i dont know what you explained in video. But can u write down the editorial of it about how you get the given test cases to generate the given outputs in detail please and how you solved it.

Why are u creating or checking the subsets i dont understand.

Alternative solution -

  1. Initialize answer = 1.
  2. Iterate over array B and multiply the answer by pow(2, count of set bits of last element). Don’t forget the modulus operation.
  3. If the count of set bits of the current element is less than that of the last element, then the answer is zero.

Solution

Can you explain it in a little bit more detail?

brother , can you help me how to approach this type of problems…
your codes are simple , but i don’t know how to approach this type of problems,
please help.

I don’t know how to explain. It just comes naturally. Just keep brainstorming, I guess.

1 Like

This can give wrong answer.
Third point is incomplete . According to u answer for {2,4,8} is 4 but shouldn’t the answer be 0.

He’s checking the subsets because in List B, an element at position “i”, is the result of OR operation on all the elements before index i in list A.

this means, let list A ( this list is not given in the testcase) is [A1, A2, A3…], then the list B, which is given to us in the test cases, is formed as follows :-
B1 = A1
B2 = A1 OR A2
B3 = A1 OR A2 OR A3
Bn = A1 OR A2 OR A3…OR An

thus for each pair of elements of list B,
B[i] AND B[i+1] = B[i] (AND operation)
So, this is the reason why he checks that condition, now if any pair does not satisfy this condition,

for example, {7,2} , then 7 AND 2 is not equal to 7, so the condition is false.
This means that such a list, cannot be formed by any numbers, or for this combination, no list A exists. Thus, in this case, answer = 0.

I hope that this was helpful.

2 Likes

Thanku @kabirpathak for the explanation, i got it now. Actually i was not reading the question carefully and thinking the sequence given as sample input is Ai but as it turns out it was Bi. Now i got it. Although thanks for the And check part, in live contest i must have have got penalties for that. Yay thank you man.

1 Like

when we got c
then we have to calculate the 2^c; and answer is ans = ans*2%MAX
that the answer

@m_tab you’re right. I think the third point should be something like this :

If the count of set bits of the current element is less than that of the last element, then answer = 0.
Also, if the count of set bits of the current element is equal to that of the last element,
then,
a.) if current and last element are equal, continue the process;
b.) if current and last element are different, answer = 0;

What do you think?

EDIT: No, the approach is wrong. If we consider the following list B, {2, 6, 7}
Then according to this approach, the solution should be 2^5 = 32, since
the number of set bits in 6 = 2, and in 7 = 3.Hence, 2 + 3 = 5. 2^5 = 32.

              But, here the correct answer is 8. So, this approach is incorrect.