MYSARA problem

help
, ,
1

What is wrong in this code ?

#include<iostream>
#include<algorithm>
#define ll long long int
#include<cmath>
using namespace std;
ll power(ll x, ll y) 
{ 
    if (y == 0) 
        return 1; 
    else if (y % 2 == 0) 
        return power(x, y / 2) * power(x, y / 2); 
    else
        return x * power(x, y / 2) * power(x, y / 2); 
}
main()
{
	ll t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		ll a[n];
		ll x[n];
		ll ex[n];
		ll ans;
		x[0]=0;
		ex[0]=0;
		ans=0;
		for(ll i=0;i<n;i++)
			{
			cin>>a[i];
			
			if(i>0)
				{
				if(a[i]<a[i-1])
				{
					ans=0;
					break;
				}
			
				ll temp=a[i]&a[i-1];
			//	cout<<temp<<endl;
				ll c=0;
				while(temp!=0)
				{
					c+=(temp%2);
					temp=temp/2;
				}
				ex[i]=c;	
				if(c>=1 && ans==0)
					ans=1;
				
				if(ex[i]!=0)
				{
				
				ans=ans*((ll)(power(2,ex[i]))%1000000007);
				
				}
				ans=ans%1000000007;
				}
			}
		if(n==1)
			ans=0;	
		cout<<ans<<endl;
	}
	
}
2

The answer will be wrong for the testcase

1
2
7 8

The sequence is increasing, but there are bits that are unset, so there is no possible sequence. To make sure no bits are unset, use
a[i-1]&a[i] == a[i-1]. This makes sure there are no bits that are one in a[i-1] but 0 in a[i]. It also checks whether a[i-1]<=a[i] because a&b is always less than or equal to both a and b, so if a[i-1] is greater, it cannot be equal to a[i-1].

Why is answer 0 if n==1? If n=1, means there is one answer, the number itself.

Why is answer reset as 1 everytime you get c>=1?

3

If n==1 its my mistake it should be 1
i initialize ans with 0 so if i multiply any number it will always showl 0 so if c>=1 means we have possible sequence and hence im initailizing ans=1;
and this is only one time process because another condition is ans==0;

4 
1
2
0 1

That condition might be causing some problems.

5

my code is giving 0

6

Is it? I think it’s 1.
The sequence A={0,1} satisfies the given B.
Assuming c>=1 is risky, since 0 has no set bits.
Instead you can start with ans=1, and set it to 0 only when you see an impossible case.

7

you are right…
It should be 1 but then why i get AC
please check test case
And i want to know that how can i ignore some input because im breaking in mid way. SO i think it is creating a problem

8

cin.ignore() To ignore the rest of the input in the line. Remeber you only go to the next line when you attempt to read from an empty line, NOT when there is no more input in the line.
The testcases were horrendously weak for this question.

9

thanks :blush:

10

@everule1 Will we have the editorial for this problem?

11

We will when the editorialist finishes writing the editorial. It is very difficult to write understandable editorials so it takes a lot of time.

1 Like
12

Now i think its all correct .
Please help

#include<iostream>
#include<algorithm>
#define ll long long int
#include<cmath>
using namespace std;
ll power(ll x, ll y) 
{ 
    if (y == 0) 
        return 1; 
    else if (y % 2 == 0) 
        return power(x, y / 2) * power(x, y / 2); 
    else
        return x * power(x, y / 2) * power(x, y / 2); 
}
main()
{
	ll t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		ll a[n];
		ll x[n];
		ll ex[n];
		ll ans;
		x[0]=0;
		ex[0]=0;
		ans=1;
		for(ll i=0;i<n;i++)
			{
			cin>>a[i];
		}
			ll c=0;
			
		for(ll i=0;i<n;i++)
		{
		
			if(i>0)
				{
				if(a[i]<a[i-1])
				{
					ans=0;
					break;
				}
				c=0;
				ll temp=a[i]&a[i-1];
				while(temp!=0)
				{
					c+=(temp%2);
					temp=temp/2;
				}
				ex[i]=c;	
			
				
				if(ex[i]!=0)
				{
				
				ans=ans*((ll)(power(2,ex[i]))%1000000007);
				
				}
				ans=ans%1000000007;
				}
			}

		cout<<ans<<endl;
	}
	
}
13

You got an AC. I mean the code will still fail for

1
2
7 8

But that doesn’t really matter i guess.

14

image
image690Ă—535 7.92 KB
Here is what i get

15

i think it is correct!

16

It’s 0.

18

so what is condition for that…
Sorry , i know it hurt you for replying to such a silly question and person like me…who knows little about CP

And is the condition is

a[i-1]&a[i]==a[i-1]

19

Yes.

Sorry , i know it hurt you for replying to such a silly question and person like me…who knows little about CP

No. I want more people to like and become better at cp, so I try to help as many beginners as I can so they don’t feel frustrated.

3 Likes
20

well my code
https://www.codechef.com/viewsolution/30682880
works fine for
1
2
7 8
as well…still it gives WA.
Could you please help?

21

Overflow on answer. ans[i] can be up to 10^9 and so can answer. 10^{18} will most definitely overflow an int.
https://www.codechef.com/viewsolution/30683883

1 Like