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 zerobased 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 nondecreasing 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.
This question is marked "community wiki".
asked 23 Oct '17, 02:57
