All Tracks Algorithms Sorting Merge Sort Problem

Median Game
Tag(s):

Algorithms, Easy, June Easy 19, Logic-Based, Merge sort, Sorting

Problem
Editorial
Analytics

You are given an array \(A\) of \(N\) integers. You perform this operation \(N - 2\) times: For each contiguous subarray of odd size greater than \(2\), you find the median of each subarray(Say medians obtained in a move are \(M_1, M_2, M_3,\ldots, M_k\)). In each move, you remove the first occurrence of value \(min(M_1, M_2, M_3,\ldots, M_k)\) from the original array. After removing the element the array size reduces by 1 and no void spaces are left. For example, if we remove element \(2\) from the array \(\{1, 2, 3, 4\}\), the new array will be \(\{1, 3, 4\}\).

Print a single integer denoting the sum of numbers that are left in the array after performing the operations. You need to do this for \(T\) test cases.

Input Format

The first line contains \(T\) denoting the number of test cases(\(1 \le T \le 10\)). 

The first line of each test case contains \(N\) denoting the number of integers in the array initially(\(4 \le N \le 10^5\)).

The next line contains \(N\) space seperated integers denoting \(A_1, A_2, A_3,\ldots, A_N\)(\(1 \le A_i \le 10^9\) for all valid \(i\)).

Output Format

Output a single integer denoting the sum of numbers left in the array after performing the operations for each test case on a new line.

SAMPLE INPUT
2
4
2 5 3 2
4
1 1 1 1
SAMPLE OUTPUT
7
2
Explanation

For the first test case:  Initially, array is \(\{2, 5, 3, 2\}\). The medians obtained are \(\{3, 3\}\) for subarrays \([1, 3]\) and \([2, 4]\) respectively. Hence, we remove \(min(3, 3) = 3\) from the initial array. The array now becomes \(\{2, 5, 2\}\). The median of the whole array is \(2\). Hence we remove the first occurrence of \(2\) from the array. So, we are left with \(\{5, 2\}\) in our array.

 For the second test case, it is obvious that the minimum medium will be \(1\) every time. Hence finally, we will be left with \(\{1, 1\}\) as the array.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

June Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?