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

×

CK87MEDI Editorial

Problem Link:

Practice

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.

Solution 1

Solution 2

This question is marked "community wiki".

asked 23 Oct '17, 02:57

saeed_sryhini's gravatar image

3★saeed_sryhini
152
accept rate: 0%

wikified 23 Oct '17, 03:05


Remaining editorials ?

link

answered 23 Oct '17, 20:32

tihorsharma123's gravatar image

2★tihorsharma123
49718
accept rate: 15%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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