What in the world is wrong with this code?
Can someone please have a look at my submission to this problem : CodeChef: Practical coding for everyone
Actually i was trying similar conditions(by observing test cases) , and this one worked.Although i have a little intuition about this , but i want to know if this method passed due to weak test cases or is it correct method.
Thank you.
I have to say, I have no clue why it is not accepted.
1 Like
What about
1
1
3 5 10
As the setter mentioned you also need to check the cumulative orās in the reverse direction
I donāt really understand this editorial, it lacks sufficient rigor and explanation clarity. The editorial seems to suggest that whenever we have more than 62 numbers in the input array, it will always happen that we will find different indices i and j such that all the bits that are set in A[i] are also set in A[j].
Well, this is clearly not true. For a counterexample, let numberOfBits = 4, n = 6 and consider the following 6-element array of 4-bit integers: A[] = \{0 0 1 1, 0 1 0 1, 0 1 1 0, 1 0 0 1, 1 0 1 0, 1 1 0 0\}.
Even though 6>4, we cannot find different indices i and j such that all the bits that are set in A[i] are also set in A[j].
Can somebody explain in a clear and mathematically correct and formal manner what exactly condition holds when the number of elements is bigger than the number of possible bits?
Many people are mentioning the pigeonhole principle, but no-one has clearly elaborated what they actually mean.
When the number of elements is bigger than the number of possible bits, the only thing which follows from that is that: there exist at least two different indices i and j such that the numbers A[i] and A[j] share at least one of their set bits (provided that we have at least two non-zero elements. If all elements are zeroes, or all-but-one are zeroes, this statement does not hold). It doesnāt follow that there exist at least two different indices i and j such that all the bits that are set in A[i] are also set in A[j].
Thanks for pointing out.
So if i include the check in reverse direction also ,then it becomes better(in terms of time complexity) than the other method that uses set ?
Actually not, but that lies with the intricacies of the big O notation
The set solution has runtime in the order of n^2 for n\leq 60 and constant for n> 60.
Because of how big O notation is defined this will mean that the complexity of the set algorithm will be O(1) which is quicker than the O(n) of the cumulative or. Of course completing the I/O routines will be O(n) so in the end they have the same complexity.
2 Likes
I have already added one.
1 Like
I dont understand ,why only n(n+1)/2 ???
isnāt 2^n the formula of no. of unique subsequences??
So, is n(n+1)/2 the formula for tot. no. of contiguous subsequences???
plez explain why only n(n+1)/2???
Yes
contiguous subsequences = Subarrays
1 Like
see i will try to explain you by using 6 bits. suppose if 6 bits was the only required size(which means if 1<=A<=63). Then if N > 6 , then print NO. By this means it should contain only 6 or less elements, such that all element should set(=ā1ā) atleast one new bit which was not set in all previous elements. so what could be one of the possible set{100000,010000,001000,000100,000010,000001} ===> so if OR any (l,r) pair elements from this set it will be unique. so lets see what if we take n=7??? can u tell any no. which can be represented in 6 bits and IT SETS A BIT WHICH IS NOT PREVIOUSLY ALREADY SET BY ANY OTHER ELEMENT ??? ==> NO, not possible , since already every bit is set already .
(continuing above example)
a1=32
a2=16
a3=8
a4=4
a5=2
a6=1
LETS TAKE ONE MORE ELEMENT any random no. a7=7=000111(in 6 bits)
so let take two pair of (l,r) which are (4,6)and(7,7)and compare there OR value
for(4,6)= 000100|000010|000001=000111
for(7,7)= 000111 so you can see these two values are not unique. Similarly you can take any value from 1 to 63 and check instead of 7 , there will be atleast two such pair whose OR value will be same.
HOPE so this explanation will be of some help to you.
1 Like
Can anyone tell me what is wrong with my solutionā¦ I m not getting any wrong test caseā¦
Could you give an explanation of what your main loop is supposed to do? I am having trouble understanding the idea behind the code so I canāt really judge why it is not correct.
Hi, I figured out the forward case but cannot figure out why we need to check reverse case from n-1ā¦0. Could you please provide a test case?
Can you explain why we need to take to suffix OR or provide with some test case to run with? I am getting all correct answers of all the test case I am generating.
void solve() {
int n;
cin >> n;
unsigned long long mask = 0;
bool found = true;
for(int i = 0; i < n; ++i) {
unsigned long long num;
cin >> num;
unsigned long long pm = mask; // prev mask
mask |= num;
if (mask == pm) found = false;
}
if (found) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
1
2
1 3
The problem is that for the prefix algorithm to return āNOā, there have to be two subarrays with the same OR-value, and these subarrays have to end at different indexes. The case where such subarrays have the same end index is therefore missed, but is catched by also checking suffixes in a similar way as in the prefix algorithm.
#include <iostream>
using namespace std;
int main() {
// your code goes here
int t; cin>>t;
while(t--){
int n ; cin>>n;
long a[n];
for(int i = 0 ; i< n ; ++i )
cin>>a[i];
long val = a[0] ;
bool c = 1;
for(int i= 1; i < n ; ++ i ){
if((val & a[i] ) == a[i])
{
c = 0; break;
}
else val = val | a[i];
}
if(!c) cout<<"NO"<<endl;
else {
c = 1;
val = a[n-1] ;
for(int i = n-2 ; i>= 0 ; -- i )
{
if((val&a[i]) == a[i]){
c= 0 ; break;
}
else val = val | a[i] ;
}
if( c ) cout<<"YES\n";
else cout<<"NO\n";
}
}
return 0;
}
O(N) approach
From left to right if answer is YES then I again check from right to left.
I have considered all possible subarrays and performed bitwise OR on it elements.
The logic is thatā¦ i have calculated the partial results of OR and pushed it back again in the vector for further calculation.
I have tried many different test cases , it works fineā¦ But gave WA when submitted 
Please help me with thisā¦
Can anyone explain Why this gives WA CodeChef: Practical coding for everyone
BUT THIS GIVES AC CodeChef: Practical coding for everyone