11429 - Randomness

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11429 - Randomness

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.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11429 - Randomness

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: 11429 - Randomness

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
``````
Last edited by sclo on Tue Mar 25, 2008 1:46 am, edited 3 times in total.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11429 - Randomness

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.
Last edited by Robert Gerbicz on Tue Mar 25, 2008 2:09 am, edited 1 time in total.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: 11429 - Randomness

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.