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

×

MXMEDIAN - Editorial

Problem Link

Practice

Contest

Author: Praveen Dhinwa

Tester: Pawel Kacprzak and Misha Chorniy

Editorialist: Bhuvnesh Jain

Difficulty

EASY

Prerequisites

Greedy, Sorting, Median

Problem

You are given an array $A$ of size $2 * N$ consisting of positive integers, where $N$ is an odd number. You can construct an array $B$ from $A$ as follows, $B[i] = max(A[2 * i - 1], A[2 * i])$. Consider all permutations of $A$. Print any one of them which maximises the median of $B$

Explanation

The larger elements we have in the array $B$, the larger will be its median. Since, array $B$ has $n$ elements only, we would like to have the largest $n$ elements of $A$ somehow, go into the array $B$. Let us assume we have a black box which permutes array $A$ in some manner such that the largest $n$ elements go into array $B$. Now, what will be the median of array $B$ in such a case? It will be simply the middle element once the array $B$ is sorted.

Now, let us describe the black box now. We see that elements of $B$ are from adjacent elements from $A$. i.e. they are independent of each other in their selection. Thus, we simply put all the highest $n$ elements in either odd or even positions in array $A$. This will ensure that are always selected into array $B$. So, the only requirement is to sort the array $A$ to get the highest $n$ elements. The sorting can be done using mergesort, randomised quick-sort or any inbuilt sort function available.

The above is just one of the methods to construct the array and solve the problem. Multiple solutions to the problem might exist. Feel free to discuss them below.

Time Complexity

$O(n \log{n})$ per test case

Solution Links

Setter's solution

Tester's solution

Editorialist solution

This question is marked "community wiki".

asked 18 May '17, 13:46

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

edited 23 May '17, 18:11

admin's gravatar image

0★admin ♦♦
19.8k350498541


My solution is almost similar to the Editorialist solution but i got WA where am i wrong https://www.codechef.com/viewsolution/13499478

link

answered 18 May '17, 17:15

divik544's gravatar image

4★divik544
5251110
accept rate: 10%

Your answer is correct, but the array required to give that answer is is incorrect, after sorting your array would look lie
a[0],a[1],a[2],a[3],.......a[2n-1]
but the array which gives required answer will look like
a[0],a[n],a[1],a[n+1].....a[n-1=,a[2
n-1].

(18 May '17, 17:53) swamicoder4★

@divik544 You sorted the initial array, but you forgot to permute it! Remember, you need max elements in each adjacent pair of elements. If the array is a0, a1, a2, a4, ... a(2n-1) after sorting. A valid permutation would be: a0, an, a1, a(n+1), ... a(n-1), a(2n-1) after which the B array becomes an, a(n+1), a(n+2), ... a(2n-1) and the median would be a[(3n-1)/2] that is, [(n) + (2n-1)]/2. Here's my solution

link

answered 18 May '17, 17:39

arvindpunk's gravatar image

3★arvindpunk
632
accept rate: 7%

edited 18 May '17, 17:42

******************************************/
#include <bits/stdc++.h>
using namespace std;

typedef long long LL; 
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;

int main() {
    #ifndef ONLINE_JUDGE
        freopen("inp.txt", "r", stdin);
    #endif

Could someone please explain how we are saving time through this in programs? As I am new to programming.

link

answered 10 Jun '17, 14:21

adiaspirant's gravatar image

2★adiaspirant
1
accept rate: 0%

edited 10 Jun '17, 14:44

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066

How do you edit code to preview in readable format @vijju123 ?

(10 Jun '17, 14:48) godslayer121★
1

Copy paste the entire code, then select it, and THEN click "Enter code"

(Make sure to give atleast 1 space to code from any sentence before or after the code, else it wont have any effect)

Eg-

`Have a look at my code
#include.... //This is wrong`

`Have a look at my code

#include...//this is right`
(10 Jun '17, 14:51) vijju123 ♦♦5★

Thanks mate ! ^-^

(10 Jun '17, 14:58) godslayer121★

@adiaspirant, we just saving some tying time by these statements and nothing else. The ifndef statement just helps us to execute the code directly from sublime text without going to the terminal again and again. The ifndef statement will only work when the "ONLINE_JUDGE" flag is defined while compilation which can be seen on the specific websites.

(17 Jun '17, 14:03) likecs6★

Setter & Tester solution links not yet updated :(

link

answered 10 Jun '17, 14:35

godslayer12's gravatar image

1★godslayer12
419210
accept rate: 7%

link

answered 17 Jun '17, 10:19

vineeta1995's gravatar image

2★vineeta1995
1
accept rate: 0%

Simple and Elegant : Code

Time Complexity: O(2NLOGN)

Space Complexity: O(2N)

link

answered 28 Oct '17, 12:46

bhagirathi08's gravatar image

3★bhagirathi08
01
accept rate: 0%

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
×1,424
×176
×3

question asked: 18 May '17, 13:46

question was seen: 1,386 times

last updated: 28 Oct '17, 12:46