PROBLEM LINK:Author: Aleksa Plavsic PROBLEMProfessor Gukiz has N students number 1 through N. Let's denote the number of candies given to the ith student by P_{i}. As GukiZ has a lot of students, he does not remember all the exact numbers of candies he gave to the students. He only remembers the following properties of the sequence P.
Given the DIFFICULTYEasy EXPLANATIONLet's read the numbers remembered by GukiZ and sort them in increasing order. Let's start with the smallest number in the array. Let's suppose that for each number given the forth condition holds. That means that we can add numbers greedily starting from maximum possible value (and ignoring numbers given so we don't add them twice). Let's suppose that this condition isn't satisfied for some numbers. That means we need to add at least one number (maybe more) so each number has another one in the set with difference no more than D. The optimal approach is to add the biggest possible numbers. So we should start from the smallest given number and check the number immediately after it, if the difference is no more than D then we can include them both. We apply the same operation for each number afterwards, checking the immediately previous and the immediately next number. If at least one of them has difference no more than D we don't need to add anything. If we had a situation where there's a number A with no match, the optimal situation is to add A+D to our set (we added the biggest value that satisifies the condition and also covers as many as possible from the upcoming numbers). We continue with this operation till we finish the array. A case that we should be careful about, is that we have a number A with no match (again by match we mean such B that A  B <= D) and we can't add A+D because it exceeds the maximum. We just add the maximum possible number X. There is a case where our number A=X we just add X1. Uptill now , we completed the list of our number such that each number has a match. If the number of needed numbers insertions is less than NK then our answer is 1 for sure. Now, we need to complete our set till it has exactly N numbers. We need only to handle the case which we have only 1 number remaining. Then we should add a number that has a match within the set we completed. In this case let's say MX = the maximum number in our array. start from min(X , MX + D) in decreasing order, and find the maximum number that doesn't exist in our array. In cases we have more than 1 number to add. We can start adding values from X. Let's add X to our set. After that, let's look at our set. By simple observation, we can see that we must start from last 2 biggest numbers, and add all numbers between them. After that we skip to 2nd biggest and 3rd biggest and add all numbers between them and so on, until we complete our set. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's/Editorialist's solution can be found here. asked 29 Aug '18, 19:31

The problem links are wrong. They are pointing to PROBSET rather than GHMC. answered 02 Sep '18, 11:15

I spent a ridiculous amount of time trying to solve the wrong problem on this one. I was wrongly trying to make it so that the maximum gap in the number of candies was no more than $D$. Once it finally became clear to me that all is needed is to ensure that each count has a nearby companion count, you can quickly convert the data to something suitable to reuse the solution for GUZAC. For speed I didn't actually add elements to the given array, just totalled the extra items that would need to be added, since I already had a fast way to find out where a denselyadded set of counts would overlap the original given set which I could iterate over a few times as I added the counts required for the $D$ constraint. answered 29 Aug '18, 20:59

Explanation 5th Para : "If the number of needed numbers insertions is less than NK then our answer is 1 for sure". answered 02 Sep '18, 18:39
