e-maxx's blog

By e-maxx, 14 years ago, translation, In English
Solution for this problem consists of two stages. First stage - counting the numbers with 1 as their first digit in the [L;R] segment. Second stage - using this information (in fact, by given probabilities that i-th quantity will be good) solve the problem about K percents.

To solve the first sub-problem one can generate all segments of good numbers and look how many numbers from them lie in the [L;R] segment. Segments of good numbers are of form [1;1], [10;19], [100;199] and so on, that is, [10i;2· 10i - 1]. After noticing that, calculating their intersection with [L;R] segment is quite easy.

So, we've learnt how to calculate the probability p[i] that i-th quantity is correct: this probability p[i] equals to a fraction of the number of good numbers and R[i] - L[i] + 1.

Now we can go to the second stage of the solution: solving the problem with N quantities and K percents. Now we know the probabilities p[i] that this or that quantity is good, and want to find the probability that K percents of them will be good. This can be done using dynamic programming: let's D[i][j] - probability that among first i quantities exactly j will be good. The starting state is D[0][0] = 1, and calculation of other states can be done as following:

D[i][j] = p[i - 1]· D[i - 1][j - 1] + (1 - p[i - 1])· D[i - 1][j].

After that answer to the problem will be a sum of D[n][j] over all j such, that j / n ≥ k / 100.
  • Vote: I like it
  • +18
  • Vote: I do not like it

14 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it
hi

why you dont put any tutorial about problem A and problem B ?

although these are simple(maybee!) but i hope you put them ,

by the way , thanks.....
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I was just wondering, if the second part (DP) could be solved in < O(n^2). Is there any way?