For this problem, how would one find the optimal solution?
Let g = lcm(b1,b2,...,bn).
If R>=g, then the problem is pretty trivial.
I don't really know how to find the optimal solution for the other case. I can find a solution, but don't see why it is optimal.
11429  Randomness
Moderator: Board moderators

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: 11429  Randomness
My greedy method is independent on the the value of g.sclo wrote:For this problem, how would one find the optimal solution?
Let g = lcm(b1,b2,...,bn).
If R>=g, then the problem is pretty trivial.
I don't really know how to find the optimal solution for the other case. I can find a solution, but don't see why it is optimal.
[I haven't proved that my greedy solution is correct, but it works.]
Re: 11429  Randomness
I haven't tried it but it seems to work. Sort the ai/bi in nonincreasing order, then we consider a1/b1 and try to decide it as soon as possible, with the fewest number of calls to RNG. If it can't be exactly decided, then replace a1/b1 with the difference with the decided fraction.Robert Gerbicz wrote:My greedy method is independent on the the value of g.sclo wrote:For this problem, how would one find the optimal solution?
Let g = lcm(b1,b2,...,bn).
If R>=g, then the problem is pretty trivial.
I don't really know how to find the optimal solution for the other case. I can find a solution, but don't see why it is optimal.
[I haven't proved that my greedy solution is correct, but it works.]
Edit: This is probably a good case to consider:
Code: Select all
Input:
2 5
1 5 1 5 1 5 1 5 1 5
Output:
3.600000
Last edited by sclo on Tue Mar 25, 2008 1:46 am, edited 3 times in total.

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: 11429  Randomness
My AC code returns by 3.600000sclo wrote: Is the solution correct?Code: Select all
Input: 2 5 1 5 1 5 1 5 1 5 1 5
[don't forget, that :"Input will be terminated by a line containing two zeros."]
Ps. I've proved that the greedy solution is correct in all cases.
Last edited by Robert Gerbicz on Tue Mar 25, 2008 2:09 am, edited 1 time in total.
Re: 11429  Randomness
Thanks, I found a bug in my reasoning. I think it's correct now. Anyway, it's based on Rary expansion of the fractions.Robert Gerbicz wrote:My AC code returns by 3.600000sclo wrote: Is the solution correct?Code: Select all
Input: 2 5 1 5 1 5 1 5 1 5 1 5 Output: 4.400000
[don't forget, that :"Input will be terminated by a line containing two zeros."]
Ps. I've proved that the greedy solution is correct in all cases.