ORTHODOX - Editorial

editorial
, , , ,
171

Could you prove why? In that case, we’re done right? I know how to continue after this is proved. I just need a solid proof that what I said is true

172

Did you try reading the editorial? Can you scroll up and read setters’s remarks?

173

thnx bruuh… it worked but cant understand for which case it could go wrong for my previous submission. I think it should cover all the test cases :thinking: :thinking:

174

The problem can be done in O(n) as well.

175

Adding each number has to add 1 or more bits to the OR, otherwise the OR doesn’t change.
Since we can’t add more than ~62 bits, we can’t add more than 62 numbers.

1 Like
176

simple idea is if we asuume o(a,b) o(c,d) are equal then we acn find some o(0,e)==o(0,f)
so it is equivalent to check o(0,L) ,L from 0 to n-1 are distinct

177

Plz anyone tell me…Why is the answer always NO after n>=62 ?

178
  1. If number of elements is more than 62, Why is the answer NO?
    Sure, maximum possible number in the array is 10^18, hence any number has less than or equal to 62 bits in its binary form. But there are 2^62 possible numbers.
  2. Both the solutions of tester and setter are in O(N^2) time complexity. Is there any other solution with lesser time complexity?
179

If we will bruteforce all possible range as said, then i think the solution will exceed the time limit.

180

suppose all elements in array are in power of two then it will go to 62 in wrost case [1,2,4,8,16,32,64,128,256,512,…so on ].

181

How?? I did it in 0(nlogn).I store all array elements in map and Just taking OR of consecutive elements and checking if it is already present or not in map.If it is present then break else add this curr OR value of array to map.

182

Thanks.

183

plse share code or try tc
1
3
12 2 7 and see if ans is coming yes or no. If no then correct and if yes then wrong.

184

Bro, number new generates from OR is non repeated iff when new number contribute towards a differnet bit. So there 62 bits now if ‘n’ is more than that then you will not able to generate a new number because it required one extra bit. I hope you understand.

1 Like
185

One more soln which gets an AC but shouldnt get an AC. If you can add test case against it in practice.

186

I have done exactly the same, taking prefix OR and suffix OR and the solution got AC.
orthodox solution

188

My code is the same as in the editorial. Only difference is that I used unordered set, and instead of finding the pointer to the element, I found it’s count. Why is it giving wrong answer? Can anyone please help?

189

Also, how do I format the code?

190

Using three backticks:

``` lang
<beautifull code>
```
1 Like
191 
#include <bits/stdc++.h> 

using namespace std;
typedef long long ll;
#define forr(i,b) for(int i=0;i<b;i++)
#define all(v) v.begin(), v.end()
#define pb(a) push_back(a)
const int N=2e6+5;
const int MOD=1e9+7;

void solve()
{
	int n;
	cin>>n;
	vector<int> a(n);
	forr(i,n) cin>>a[i];
	if(n>60)
	{
		cout<<"NO\n";
		return;
	}
	unordered_set<ll> s;
	ll cur;
	bool ok=true;
	forr(i,n)
	{
		cur=0;
		for(int j=i;j<n;j++)
		{
			cur|=a[j];
			if(s.count(cur))
			{
				ok=false;
				break;
			}
			s.insert(cur);
		}
		if(!ok) break;
	}
	if(ok) cout<<"YES\n";
	else cout<<"NO\n";
}

int main() {
  ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  	int t=1;
  	cin>>t;
  	while(t--)
  	{
  		solve();
  	}
  /*try
  {
  	int * myarray = new int[1000000000]; 
  }
  catch(std::bad_alloc & exception)
  {
  	std::cerr<<"bad_alloc detected:"<<exception.what();
  }*/
  return 0;
} ```