PROBLEM LINK:
Author: Aleksa Plavsic
Tester: Hussain Kara Fallah
Editorialist: Hussain Kara Fallah
PROBLEM
Professor Gukiz has N students number 1 through N. Let’s denote the number of candies given to the i-th student by Pi. 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.
- The numbers of candies given to each of the first K students P1, P2 … PK are known exactly.
- All elements of the sequence P are distinct and positive.
- GukiZ didn’t give more than X candies to any student (the maximum value in the sequence P is not greater than x).
- For each student i , there is at least one other student j such that | Pi − Pj | ≤ D.
- The professor gave out the biggest possible total number of candies. The sum of elements of sequence P is the maximum possible.
Given the
DIFFICULTY
Easy
EXPLANATION
Let’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 X-1.
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 N-K 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.