ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1816. Troubles with Pollard

need help!
Posted by luckysundog 23 Oct 2011 04:55
Please describe answers for two sample tests(12 and 8). Is it *mathematical expectation* or what? How is it computed?
Re: need help!
Posted by svr 23 Oct 2011 05:25
recursion =>tree ( decision tree) with edges weighted by probabilities.
Consider terminal nodes 1,...,n, which contain primes. Prob p(i) for each terminal is prob of path from tree root to node = product of probs on edges.   Let g(i) number of gcd calculations for each terminal. Mean = sum of p(i)*g(i).
Let we have 8=2^3- root. From it going out 4 edges: r1=2*(2*k+1) with p1=0.25,
and going to v=2-terminal and v=4-recursion, r2=4*(2*k+1) with p1=0.125 also in v=2
and v=4 and r3=(2*k+1) with p3=0.5 - loop in v=8, r4= 8*k with p4=1/8- loop to 8. Loops correspond to infinite geometric progression.

we have F(8)=(1/2 +1/8)(F(8)+1)+(1/4+1/8)(F(4)+1)+(1/4+1/8)*(F(2)+1)
where F(2)=0. By the way: 1/8+1/2+1/4+1/8=1 - this must be for earch inner node.

Edited by author 23.10.2011 06:03

Edited by author 23.10.2011 06:12
Re: need help!
Posted by luckysundog 30 Oct 2011 04:55
Thank you, svr, you really helped me.
But let me fix you:
F(8) = (1/2+1/8)*(F(8)+1) + 1/4*(F(2)+F(4)+1) + 1/8*(F(4)+F(2)+1)

got AC using this approach

Edited by author 30.10.2011 05:23