ORTHODOX - Editorial

editorial
, , , ,
93

@admin please rectify this. In this recent question also this mistake was made. Twice in such a small duration is not fair for many users. Please recheck the submissions.

3 Likes
94

i am not taunting you dude…i am just trying to motivate u… dont focus on these ill things (such as codes available on net)…just focus and develop ur skills

5 Likes
95

i totally agree with u
submissions should be rejudged

1 Like
96

Many Suffer When Solutions Passes with weak test cases.It’s Totally No fair!!

3 Likes
97

Very very weak testcases (if there are at all other than samples).
My solution has a bug where I don’t read input array for the case when N > 70, and just say NO, and it still passes.
https://www.codechef.com/viewsolution/35779164

3 Likes
98

suppose OR value till “i” is 00010100000
now adding one more element to previous subarray will either add more bits to previous OR value(eg…00010100000—>00110100000) or it may not add any bit to previous OR(00010100000---->00010100000). This arises the maximum possibility of 64 numbers ,each changes contributing to new number.

Note : You are confused with rearrange of bits vs adding of new bits.
In this case there is no rearrangement of bits in previous obtained OR values just there is
possibilities of adding of new bit…which can maximum go upto 64 bit (long long).

3 Likes
99
1 Like
100

So, there are 62 bits for a number till 10^18 right ? And what about the remaining two bits as long long is 64 bit. And it is signed so 1 bit is for storing the + or - sign. So one bit is remaining . Can anybody explain this?

101

It totally depends on you !
if you want to cheat or not :smile:

102

@rajarshi_basu nice problem. Liked the observation.
certainly wasn’t easy.

1 Like
103

how did you know? only 300 test cases?

104

i did’t understand fully why for n>62 the answer is NO.

105

The question didin’t expect O(n^2) time complexity… but it was so bad to know that people got their answers accepted with O(n^2) complexity… plz work hard on testcases…

1 Like
106

Is this solution correct?.
Can anyone suggest a test case for which this fails?.

#include <bits/stdc++.h>

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);

int t;
cin>>t;
while(t–)
{
long long int n,flag=0;
cin>>n;

    long long int a[n],i,j,ans=0;
    
    for(i=0;i<n;++i)
      cin>>a[i];
   
   sort(a,a+n,greater<long long int>());
   ans=a[0];
    for(i=1;i<n;++i)
    {
        if(ans==(ans|a[i]))
         {
             flag=1;
             break;
         }
         
        else
        ans|=a[i];
    }
    
    if(flag==1)
      cout<<"NO"<<endl;
      
    else
      cout<<"YES"<<endl;

}

 return 0;

}

107

What did you try in the attempt in which you got WA? Were you thinking of an efficient approach? I checked the submissions and most of the people have submitted the O(n^2) approach.

2 Likes
108

im submitting this now , yesterday i didn’t take part only.
can you check if it is correct?.
for all test cases.
I heard this problem has very weak test cases.

109

Hey. Fine I’ll try to understand your logic.

110

Yess I was thinking of an effiecient approach…

111

This code got accepted just now.but i want to know if there is some test case for which it doesn’t,as there is more learning in that.

112

Fine, should have tried to submit the brute force one once lol. Anyways, the n>62 thing is too much for a 2nd question in a cook-off, didn’t expect that kind of complexity. I feel that the O(n^2) approach should have been valid officially from the beginning.

1 Like