You are not logged in. Please login at www.codechef.com to post your questions!

×

# CK87MEDI Editorial

Practice

Contest

Author: Mohammad Shahhoud & Said Sryhini

Editorialist: Said Sryheni

Easy

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.

Solution 2

This question is marked "community wiki".

asked 23 Oct '17, 02:57 152
accept rate: 0%

 0 Remaining editorials ? answered 23 Oct '17, 20:32 497●1●8 accept rate: 15%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×801

question asked: 23 Oct '17, 02:57

question was seen: 560 times

last updated: 23 Jun '18, 00:09