GHMC Editorial

greedy
ltime63

#1

PROBLEM LINK:

Practice
Contest

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.


#2

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 re-use 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 densely-added 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.

Python solution


#3

The problem links are wrong. They are pointing to PROBSET rather than GHMC.


#4

Explanation 5th Para : “If the number of needed numbers insertions is less than N-K then our answer is -1 for sure”.


#5

worst problem statement and worst explanation