### harsh-apcr's blog

By harsh-apcr, history, 5 months ago,

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

• +5

 » 5 months ago, # |   +5 Auto comment: topic has been updated by harsh-apcr (previous revision, new revision, compare).
 » 5 months ago, # |   +5 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # |   0 Function rand() only returns small numbers (at least, on Windows).
 » 5 months ago, # |   0 Auto comment: topic has been updated by harsh-apcr (previous revision, new revision, compare).
 » 5 months ago, # |   0 n<=1e6ai<=1e12max. number of divisors can be (ai)^(1/3). In worst case, 1e4.Worst case time complexity : 20*1e4*1e6 : 2e11That's why you got tle.My Submission
•  » » 5 months ago, # ^ |   0 hmm.. I see, I thought number of divisors was logarithmic, but that's not trueCan you explain your submission ? Thanks
•  » » » 5 months ago, # ^ |   0 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 mp; for(int i=0;i f(len(div),0); for(int i=0;i=n){ ans=max(ans,div[i]); } }