algorithm related to finding probability [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

this is not a homwork its a problem i came across in a programming contest but could not find a solution to it.

The kingdom of Byteland contains N cities numbered 1..N. For each city i, the king assigns some money to that city for it's annual maintenance. The amount assigned is chosen randomly between ai (the minimum amount needed by that city), and bi (the maximum amount that can be assigned to that city). Note that the amount assigned to a city need not be an integer. The total tax collected this year is C.

What is the probability that the kingdom will issue a loss this year

Answer 1

I assume this is the correct statement:

The kingdom of Byteland contains N cities numbered 1..N. For each city i, the king assigns some money to that city for it's annual maintenance. The amount assigned is chosen randomly between ai (the minimum amount needed by that city), and bi (the maximum amount that can be assigned to that city). Note that the amount assigned to a city need not be an integer. The total tax collected this year is C.

What is the probability that the kingdom will issue a loss this year? In other words, what is the probability that the total amount assigned to all cities exceeds the total tax collected?

the sum of all assignment is x_0 + ... + x_i + ... + x_n If U(a,b) is a uniform number between a and b the sum of all assignment U(0, b_0 - a_0) + a_0 + ... + U(0, b_i - a_i) + a_i + ... + U(0, b_n - a_n) + a_n which is equal to a_0 + ... + a_i + ... + a_n + U(0, b_0 - a_0) + ... + U(0, b_i - a_i) + ... + U(0, b_n - a_n) all the values are known. The formula for adding uniform distributions is also known (check here): but in the programming problem you don't need to use the analytical solution, but implement something that gives you a good enough number... You should use montecarlo or something like that to simulate the probabilities... And you could also use the fact that U(0, k) = k * U(0, 1). To calculate the probability of the different values of the sum, and then compare them to C.