yangchang's blog

A new algorithm for the 01-OV(orthogonal vector) problem with random data
By yangchang, history, 3 hours ago, In English

I solved this problem using a method similar to ‘search pruning’. I found that the expected complexity of this method is guaranteed by running the code.

How can I prove it mathematically rigorous?

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;

struct{int s[2];}t[maxn * 64];
int tot;
void ins(unsigned long long x){for(int i=64,u=0;~--i;u=t[u].s[x>>i&1]?:t[u].s[x>>i&1]=++tot);}
void dfs(int u,int v,int _d){
	if(!_d)cout<<"YES",exit(0);
	for(int c:{0,1})for(int d:{0,1})
		if(!(c&d))if(t[u].s[c]&&t[v].s[d])
			dfs(t[u].s[c],t[v].s[d],_d-1);
}

int main() {
	mt19937_64 rng(random_device{}());
	int n;cin>>n;
	for(int i=1;i<=n;++i)ins(rng());
	dfs(0,0,64);cout<<"NO";
}
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain the problem you are solving and the code itself?

→ Reply
  • »
    »
    3 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The problem is determine if the bitwise OR of two numbers is all 1 in binary.

    He uses a Trie to keep track of all the numbers, and then traverses the Trie almost brute force and checks.

    → Reply
»
2 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

It's something $$$O(\min((\frac{4}{3})^w,n^2))$$$ under random data, nothing new.

→ Reply