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