Help in solving a randomized algorithm problem

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3442
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
2	atcoder_official	162
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	nor	150

I was practicing randomised algorithm problems and I stumbled across this nice problem : https://mirror.codeforces.com/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://mirror.codeforces.com/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://mirror.codeforces.com/contest/364/submission/237449074

Комментарии (6)

Показать архивные | Написать комментарий?

harsh-apcr

12 месяцев назад, # |

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

→ Ответить

Medeali

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.

tvmpqx_8601

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

ramaaa

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

12 месяцев назад, # ^ |

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

Can you explain your submission ? Thanks

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]);
    }
}

Блог пользователя harsh-apcr