Problem Link:
Contest
Author: Mohammad Shahhoud & Said Sryhini
Tester: Hasan Jadouh
Editorialist: Said Sryheni
Difficulty:
Easy
Prerequisites :
Sorting
Problem:
Given an array of N element, you are allowed to insert K elements into it, what is the maximum value you can get?
Explanation:
The key observation here is no notice that (K < N), but what does this imply?
It means that K + N is actually smaller than 2.N. In other words, no matter what elements are to be inserted, the median will always be one of the elements already given in the input.
Now that this is settled, we can think about a simple solution. If you want to get the biggest median we can get, what elements would we insert? Of course the bigger elements we add, the more chance we have of getting a bigger median.
The simplest solution would be to insert K elements which have the value 1001 (since the constraints specify that A_i is at most 1000). After that you can simply sort the array, and get the element positioned at (N + K) / 2, given that the array is zero-based indexed.
A little smarter solution would be to notice that the inserted elements will definitely get the last K positions in the array after sorting it in non-decreasing order. Thus you can simply sort the array, and print the element positioned at (N + K) / 2, without having to actually insert K elements.
Time Complexity: O(N . log(N))
Check setter and tester solutions for the implementation.