PROBLEM LINK:
Author: Vishal Mahavar
Tester: Rushil Patel, Prasann Kumar Gupta
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Probability and Expected values.
PROBLEM:
Given an array of n ranges, where the i^{th} range is denoted by a pair of two integers X_i and Y_i. For a range of valid indices in the array, we visit each index i within the range and pick a number X_i\le V\le Y_i which is added to our score. If our score is less than M, we don’t gain a profit, else we gain a profit equal to the score collected. Find the expected value of the score if V was chosen uniformly randomly.
QUICK EXPLANATION:
We will first calculate the expected value of our loss, i.e. the value of our score if it is less than M.
For each range, create a dynamic programming table dp[i][j] denoting the probability of getting a loss of j from the first i ranges in the query range. Once we get the expected value of our loss, we can reduce it from the overall expected value of our score if the constraint of M was not there to find our expected profit.
EXPLANATION:
We will first target our expected loss. If our score is less than M, we don’t receive any profit, in other words the score is counted as a loss. Hence, we aim to find the expected value of our score if it is allowed to be less than M only. The expected profit would be the overall expected value (our expected score if there is not restriction of M) reduced by our expected loss.
To calculate the expected loss, we first have to observe that our loss can never be greater than or equal to M (because if it was, it won’t be a loss). Let us only focus on the given index range during the query, let say there are L ranges.
Define a dynamic programming dp[L+1][M], where dp[i][j] means the probability of getting a loss of j from the first i ranges. Here dp[0][0]=1 and dp[0][x]=0 for x\gt 0 should be the base cases since you will always get 0 loss from 0 ranges.
Transitions are trivial : for i\ge 1,\ dp[i][j] = \sum_{k=X_i}^{k\le min(Y_i,j)} \frac{dp[i-1][j-k]}{Y_i-X_i+1}
TIME COMPLEXITY:
O(Q\cdot K\cdot M\cdot C). Where C is the maximum bound on the value of Y_i.
SOLUTIONS:
Please share your approaches in the comments 