Last Updated: 13 Jan, 2021
Ninja And Candies
Moderate
Asked in companies
Ninja is a boy who lives in ninjaland. Every day, during the morning he gets 1 coin from his mother. He wants to buy exactly ‘N’ candies. Each of the candies cost 2 coins usually and 1 coin if it is on sale. Ninja has to buy exactly K[i] candies of the i-th type(he buys candies in the evening).
Ninjas can buy any(possibly zero) number of candies of any type during any day(if he has enough money to do it). If the candy is on sale he can buy it for 1 coin and otherwise he has to buy it for 2 coins.
There are ‘M’ special offers in the candy shop. The j-th offer (D[j], C[j]) means that candies of the C[j]-th type are on sale during the D[j]-th day.
Ninja wants to buy all candies as soon as possible. Your task is to calculate the minimum day when he can buy all the candies.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.
The first line of each test case contains two space separated integers ‘N’ and ‘M’ denoting the total number of types of candies and the number of special offers in the candy shop.
The second line of each test case contains ‘N’ space-separated integers K[i], denoting the number of candies of each type Ninja has to order.
The next M-lines contain two space-separated integers (D[i], C[i]), denoting that the candy of C[i] type is on sale on the D[i]-th day.
Output Format :
For each query, print the minimum day when the Ninja can order all candies.
Output for each test case will be printed in a new line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N, M <= 10^4
0 <= K[i] <= 10^4
1 <= C[i] <= N
1 <= D[i] <= 10^4
Here N denotes the total number of candies and M denotes the total number of special offers.
Here K[i] denotes the number of candies of the i-th type Ninjas has to order.
Here C[i] and D[i] denote that the candy if the C[i]-th type will be on sale on the D[i]-th day.
Sum of K[i]’s in each test case will be less than 5000.
Approaches
We will iterate over all possible days, which will be between 1 to 2*(sum of all K[i]). Let our current day be ‘currDay’. We will check if any valid distribution is possible for the current day.
If we had several days for some type of candies, let's use the last one, it is always not worse than some of the previous days. Then let's iterate over all days from 1 to ‘ansd’ and do the following:
- Firstly, let's increase our balance by one coin.
- Then let's try to order all candy for which the current day is the last sale day (and pay one coin per candy). If we are out of money at some moment then just say that we should order all candy that remains in this sale day during the last day for two coins per candy.
- It is true because it does not matter which types will remain because this day is the last sale day for all of these types. So, after all, we had some remaining candy that we cannot buy during sales, and the current balance. And the current day is good if the number of such candies multiplied by two is not greater than the remaining balance.
The algorithm will be-
- We will iterate from 1 to 2*(sum of all K[i]). Let current day be ‘currDay’. We will check if we can buy all candies within ‘currDay’.
- We will find the last day of sale for all the ‘M’ candies which are less than ‘currDay’ in an array/list ‘last’.
- For each day ‘i’ which is less than ‘currDay’ we will store all the jobs which have the i-th day as the last day of sale.
- Let our current money be ‘currMoney’. We copy the contents of array/list ‘K’ in an array/list ‘need’. Now for each day ‘i’ from 1 to ‘currDay’:
- Increment ‘currMoney’ by 1.
- For all candies ‘j’, which have the i-th day as the last day of sale:
- If currMoney >= need[j]:
- Subtract need[j] from ‘currMoney’.
- Set need[j] to 0.
- Else,
- Subtract ‘currMoney’ from need[j].
- Set ‘currMoney’ to 0.
- If currMoney >= need[j]:
- If 2*(sum of element of array/list ‘need’) is less than equal to ‘currMoney’, we return true. Else, we return false.
To solve this problem, we can use binary search over the answer. The key observations are-
- If we can buy every candy in ‘totDays’ days, then we can also buy it in days D > totDays.
- Similarly, If we can not buy every candy in ‘totDays’ days, then we also cannot buy it in days D < totDays.
Both of these observations are key attributes of a Binary Search algorithm with in the range [1, 2* (sum of all K[i])] .
The complete algorithm will be-
- Now we will binary search over the answer and for each ‘mid’ we can check if we can buy all candies in ‘mid’ days
- If we can buy every candy in ‘mid’ days, then set ‘high’ to ‘mid’ - 1. Else set ‘low’ to ‘mid’ + 1.
- We finally return (‘high’ + 1) as our answer.
Similar problems