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 1831. Tsyfirkin's Lesson

Are my answers correct?
Posted by bsu.mmf.team 4 May 2011 04:58
1 -> 3.901234568
3 -> 11.127676543
4 -> 14.729570346
7 -> 25.468979219
29 -> 101.642021572
666 -> 2035.625369012
2011 -> 6070.641622553
5000 -> 15037.641622575

P.S. I have WA #4
Re: Are my answers correct?
As you can verify with brute-force, your answers are wrong. Right answers to your tests are:

1 -> 3.901234567901235
3 -> 11.127669135802471
4 -> 14.729542419753088
7 -> 25.468757517434465
29 -> 101.624893271458560
666 -> 2034.088837677804600
2011 -> 6069.098765418760200
5000 -> 15036.098765432045000
Re: Are my answers correct?
Posted by bsu.mmf.team 20 May 2011 05:02
Thank you very much! It seems to be the precision problem in my first solution. But I don't understand why my program gives correct answers now. I just replaced the calculation of expected time of a group of combinations ( the total amount of them is 100 ) to calculation this for every combination separately on each iteration (of course, I did the same with array of probabilities). But I think the more very small numbers you store, the bigger precision troubles you have, isn't it?
Re: Are my answers correct?
Oh my God, you described something very difficult =) My solution fills only two linear arrays in O(N)...
Re: Are my answers correct?
Posted by bsu.mmf.team 20 May 2011 14:06
I have an array P[10][10], where P[i][j] is the probability, that Feofan remembers the combination i,j (if i or j less, than 2, then P[i][j] = 1). Then I calculate the expected time for each such combination. So, you can assume I also have 2 arrays of length 100, and my algo O(k) :)
Re: Are my answers correct?
I don't quite understand where do you need this array P[10][10]? - for any combination of digits you can easily calculate probability that he was already summing this before k-th position - it is 1-0.98^(k-1) for non-equal digits and 1-0.99^(k-1) for equal digits...
Re: Are my answers correct?
Posted by bsu.mmf.team 20 May 2011 16:02
Yes, it's true (except the combinations like 1-4). But I store this in array because of my own convenience :)

Edited by author 20.05.2011 16:13