harsh-apcr's blog

Help in solving a randomized algorithm problem
By harsh-apcr, history, 11 months ago, In English

I was practicing randomised algorithm problems and I stumbled across this nice problem : https://codeforces.net/contest/364/problem/D

My approach to this problem is as follows : Let $$$g$$$ be the ghd of the input, then prob($$$g | a_i$$$) = 1/2 (where $$$a_i$$$ is random number from the input) thus with 1/2 probability $$$g$$$ is divisor of $$$a_i$$$, so divisors of $$$a_i$$$ can be good candidate for $$$g$$$

So my algorithm is repeat 20 times : take random number $$$a_i$$$ from the input array, compute its divisors iterate over its divisors list, and for each divisor $$$d$$$ of $$$a_i$$$, compute number of $$$a_j$$$ such that $$$d | a_j$$$, if it is $$$\geq \frac{n}{2}$$$ then $$$d$$$ is candidate $$$g$$$

Probability I don't get correct answer = probability in none of the 20 trails I get the correct $$$a_i$$$ = $$$1/2^{20}$$$ approx $$$10^{-6}$$$

Time complexity of the solution is : $$$O((n d + \sqrt{A})m)$$$ ,where $$$m$$$ is number of trails, $$$A = \textrm{max} a_i$$$, and $$$d$$$ is max number of divisors (which is typically very small and grows logarithmically)

Here is my submission link : https://codeforces.net/contest/364/submission/237431910

I am getting TLE, what can be the problem ?

UPDATE : I did some optimizations, and passed the 3rd test-case now I am stuck at 4th These two test cases are very similar I don't know why there is this problem

updated submission : https://codeforces.net/contest/364/submission/237449074

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by harsh-apcr (previous revision, new revision, compare).

→ Reply
»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

i think since you have 20 times compute divisors consider computing them in a faster way(maybe sieve) it is just and idea i am not so sure.

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

    I don't think its gonna work, only thing it'll do is reduce by a factor of $$$\log A$$$ (i.e. take $$$\sqrt{A}$$$ to $$$\sqrt{A}/\log A$$$, which isn't much of an improvement, Also I tried submitting with $$$m=10$$$, it still failed at test-case 3. So, it seems unlikely that'll help

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah it was just an idea well i guess you should see editorial and try to look for an improvement maybe your idea was not so efficient.

      → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Function rand() only returns small numbers (at least, on Windows).

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by harsh-apcr (previous revision, new revision, compare).

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

n<=1e6

ai<=1e12

max. number of divisors can be (ai)^(1/3). In worst case, 1e4.

Worst case time complexity : 20*1e4*1e6 : 2e11

That's why you got tle.

My Submission

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hmm.. I see, I thought number of divisors was logarithmic, but that's not true

    Can you explain your submission ? Thanks

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      • To avoid looping through the array(arr) for all divisors of an element, you can use seive technique.

      • But array values 'arr[i]' is pretty large(1e12). So, how to use seive technique here.

      • We can mask the values of the divisors(possible gcd values) to smaller indices(can be done using map).

      sort(all(div));
map<ll,ll> mp;
for(int i=0;i<len(div);i++){
   mp[div[i]]=i;
}
      • Let 'num' be the random element of array(arr). Then, __gcd(num,arr[i]) for all 1<=i<=n will give the mapping of arr[i] to divisor of num which can be firther mapped to indices. 
      vector<ll> f(len(div),0);
for(int i=0;i<n;i++){
    f[mp[__gcd(num,a[i])]]++;
}
      • Now use seive method over it to count which indices covers more than half of the array elements.
      for(int i=0;i<len(div);i++){
    for(int j=i+1;j<len(div);j++){
        if(div[j]%div[i]==0){
            f[i]+=f[j];
        }
    }
    if((f[i]<<1)>=n){
        ans=max(ans,div[i]);
    }
}
      → Reply