yangchang's blog

By yangchang, history, 3 months 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
  • +7
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +3 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.

»
3 months ago, # |
Rev. 3   Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    您能解释一下 4/3 的来历吗?如果 $$$n=O(2^w)$$$,那么该做法复杂度显然不是 $$$O((\frac43)^w)$$$ 的啊?

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it -25 Vote: I do not like it

      不知道这个回答为啥被踩这么多,codeforces 人都他妈瞎的?一群屁都不懂废物在这瞎骂,换个红名号来评论就老实了。

      随机数据下随便两个零一矢量在某一维度不正交概率是 (1/2)^2=1/4,正交概率为 3/4,那么总共 w 位每一位正交概率就是 (3/4)^w,于此期望在找 (4/3)^w 个随机矢量对之后找到一个正交的矢量对。

      然后暴力查找所有的是 n^2 的,然后因为找到第一个矢量对之后就直接弹出了,所以是和 (4/3)^w 取 min(不过这里是期望)。

      然后你这个 n=O(2^w) 算是我不严谨?不过计算机也不太会允许你放 2^64 个数字进去吧,稍微改一下的话就是 O(max(n log n,min(n^2,(4/3)^w))?

      和 trie 没啥关系,直接全存到 vector 里然后跑 n^2 暴力和你这个差不多快。

      #include "bits/stdc++.h"
      using namespace std;
      #define int long long
      signed main() {
         mt19937_64 rng(random_device{}());
         vector<int> Q;
         int n;cin >> n;
         for(int i=1;i<=n;++i) Q.push_back(rng());
         for(int i:Q)
            for(int j:Q)
               if((i&j)==0) {
                  cout << "YES" << endl;
                  return 0;
               }
         cout << "NO" << endl;
      }
      
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you!

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        Nerd.

        Do you think a person outside China can understand this?

        You can use English to revile us,then you can get more downvotes!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Illegal language.