Page 1 of 1

11429 - Randomness

Posted: Mon Mar 24, 2008 2:11 am
by sclo
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.

Re: 11429 - Randomness

Posted: Mon Mar 24, 2008 9:34 am
by Robert Gerbicz
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.
My greedy method is independent on the the value of g.
[I haven't proved that my greedy solution is correct, but it works.]

Re: 11429 - Randomness

Posted: Mon Mar 24, 2008 10:29 pm
by sclo
Robert Gerbicz wrote:
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.
My greedy method is independent on the the value of g.
[I haven't proved that my greedy solution is correct, but it works.]
I haven't tried it but it seems to work. Sort the ai/bi in non-increasing 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.

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

Re: 11429 - Randomness

Posted: Tue Mar 25, 2008 12:34 am
by Robert Gerbicz
sclo wrote: Is the solution correct?

Code: Select all

Input:
2 5
1 5 1 5 1 5 1 5 1 5

My AC code returns by 3.600000

[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.

Re: 11429 - Randomness

Posted: Tue Mar 25, 2008 1:45 am
by sclo
Robert Gerbicz wrote:
sclo wrote: Is the solution correct?

Code: Select all

Input:
2 5
1 5 1 5 1 5 1 5 1 5

Output:
4.400000
My AC code returns by 3.600000

[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.
Thanks, I found a bug in my reasoning. I think it's correct now. Anyway, it's based on R-ary expansion of the fractions.