Last Updated: 25 May, 2022
Ninja and his Birthday Treat
Easy
Asked in company
Ninja, on his birthday, decided to give a treat to 'N' children in his neighbourhood. Ninja took every child to a nearby candy shop and bought them candies. The shop contains ‘M’ types of candies with an unlimited supply of each candy. The cost of each candy is between 1 and M, inclusive and distinct.
The shopkeeper has marked every candy with a number between 1 and M, inclusive. To make this process fascinating, Ninja found a way. He asked every child three integers, ‘L’, ‘R’, and ‘X’. Then he bought exactly ‘X’ pieces of each candy from [L to R] , i.e., “L, L+1, L+2,..., R-1, R”.
Your task is to find the lexicographically smallest array “A” of ‘M’ integers where each element represents the cost of the ith candy, such that the total cost spent by Ninja is minimum.
Note:
The cost array is a permutation of the first M natural numbers.
The shop has unlimited supplies of candies.
In case of multiple permutations, print one which is lexicographically minimum.
For example:
Let’s say ‘N’ = 3 , ‘M’ = 5
The integers told by children are { {2 , 4 , 1} ,{1 , 3 , 2} , {3, 3 , 5} }
The optimal permutation will be {3 2 1 4 5}
Costs paid by Ninja are 7, 12, and 5, respectively.
The total cost would be 7 + 12 + 5 = 24
Input Format :
First-line contains 'T,' denoting the number of Test cases.
For each Test case:
The first contains two integers, 'N' and ‘M’, where ‘N’ is the number of children and ‘M’ is the number of candies available in the shop.
Next, the ‘N’ line contains three integers, ‘L’, ‘R’, and ‘X’.
Output format :
For each test case, print ‘M’ integers, i.e., the permutation of ‘M’ natural numbers.
Constraints :
1<=‘T’<=10
1<=‘N’<=10^5
1<=‘M’<=10^5
1<=‘L’<=‘R’<=‘M’
1<=‘X’<=10^5
Time Limit: 1 sec
Approaches
Approach :
Calculate the frequency of each candy sold, and since we have to reduce our total cost, we can assign the lower price to the higher-selling candy. Hence, we will give the cost in decreasing order of their selling quantity. Assign cost 1 to most selling candy, cost 2 to the second most selling candy, etc.
Algorithm:
- Create an array ‘count’ of length ‘M’ and initialize it to 0.
- Now iterate over all the triplets “(L, R, X)” and add ‘X’ to each position from L to R, inclusive.
- Now create an array ‘A’ of size ’M’ and assign the number to candy in decreasing order of their frequency.
- Calculate the total cost by multiplying the frequency of candy by the corresponding number assigned and summing them together.
Approach :
Calculate the frequency of each candy sold, and since we have to reduce our total cost, we can assign the lower price to the higher-selling candy. Hence, we will give the cost in decreasing order of their selling quantity. To find out the number of candies sold, we could use the prefix sum. For all demands (L, R, X), add X to the Lth position and subtract X from the R+1th position of the count array.
Now take the prefix sum of the count array.
Algorithm:
- Create an array ‘count’ of length ‘M’ and initialize it to 0.
- Now iterate over all the triplets ‘(L, R, X)’ and add ‘X’ to position L and subtract ‘X’ from the ‘R+1’ of the “count” array.
- Take the prefix sum of the ‘count’ array.
- Now create an array ‘A’ of size ’M’ and assign the number to candy in decreasing order of their frequency.
- Calculate the total cost by multiplying the frequency of candy by the corresponding number assigned and summing them together.