INFOSYS TEST PROBLEM

1

CAN ANYONE HELP?

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

1<=N<=1000

1<=M<=100

0<=Xi<=100

0<=Yi<=100

Example:

N 3

M 2

X-> 1,2

Y-> 2,2

OUTPUT=3

2

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[0][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?

1 Like
4

why u deleted the post?

5

I had the dp approach, but it requires that all people are considered as same object. Also, it answer was not matching to the test case you gave.

6

All three possible ways are :
person 1, person 2, person 3
1-> (1,1) , (2,2), (2,2)
2-> (2,2), (1,1), (2,2)
3-> (2,2), (2,2), (1,1)

(d1,d2) → it means first vaccine is given on d1 and second vaccine is given on d2

7

is this solution correct?

8

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