There are N people in a country and everyone needs to be given two doses of covid vaccination. The government provided two arrays X and Y, of length M.
*Xi denotes that exactly Xi people should be vaccinated with the first dose on the ith day of vaccination
*Yi denotes that no more than Yi people should be vaccinated with the second dose on the ith day
It is given that if a person is vaccinated with the first dose on a jth day, then the second dose should be on day j or later.
Find the total no of ways in which goverment can assign day of two doses to each of the n people such that all the people are vaccinated in M days. Since the answer can be very large, return it modulo 10^9+7.
Note: It is given that the sum of all Xi is equal to N. Also it is guaran teed that Xi<=Yi
Let dp[i][j] = Number of ways till ith day with total j people.
Then, dp[i][j] = dp[i - 1][j - Yi] + dp[i - 1][j - Yi + 1] + …+ dp[i - 1][j - Xi].
So, if we construct dp in a prefix sum manner ,then
dp[i][j] = dp[i - 1][j - Xi] - dp[i - 1][j - Yi - 1]
Then, make dp[i][j] again a prefix sum.
Base case => dp[x] = 1 , x <= Xo (not Yo) and others will be 0. This is not as prefix sum.
At last, retrieve original dp from these prefix sum by taking adjacent differences. Then, ans is simply, dp[m - 1][sum of all Xis=n].
Time complexity will take in worst case as much as M.M.100 = 10^8 operations and space is M.100 = 10^5 for worst (u need only the previous for getting current)
Upd: Can you explain the output for the test case you gave?
no, I have taken all persons as same object, means only the distribution of numbers in different days is what I have posted .
The modified eq will be -
dp[i][j] = dp[i - 1][j - Yi] * C(j, Yi) + dp[i - 1][j - Yi + 1] * C(j, Yi - 1) + …+ dp[i - 1][j - Xi] * C(j, Xi)
Now, I don’t think it can be simplified like prefix sums. Then , time complexity will be M.M.100.100