Ninja and his Birthday Treat

Easy
0/40
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
Microsoft

Problem statement

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
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 5
2 4 1
1 3 2
3 3 5
2 3
2 3 1
1 2 2
Sample Output 1 :
3 2 1 4 5 
2 1 3
Explanation Of Sample Input 1 :
For testcase one:
‘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

For test case two:
‘N’ = 2 , ‘M’ = 3  
The integers told by children are { {2 , 3 , 1} ,{1 , 2 , 2}.

The optimal permutation will be {2 1 3}.
Costs paid by Ninja are 4 and 6, respectively.  
The total cost would be 4+6 = 10
Sample Input 2 :
2
4 6 
2 5 2 
1 5 1 
3 6 3
4 4 1      
4 6 
1 3 2 
1 5 1 
1 1 3
2 2 1
Sample Output 2 :
6 4 2 1 3 5 
1 2 3 4 5 6
Hint

Calculate the total amount of each candy sold.

Approaches (2)
Sorting

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.
Time Complexity

O(N*M). Where ‘N’ is the number of children and ‘M’ is the number of candies. 

We are just traversing the array of size ‘N,’ and we have to update the utmost ‘M’ position in the worst case for each element.


 

Space Complexity

O(M).

We are creating a frequency array of size ‘M’’. 

So, the Space Complexity is O(M).


 

Code Solution
(100% EXP penalty)
Ninja and his Birthday Treat
Full screen
Console