All Tracks Algorithms Sorting Merge Sort Problem

Pebbles Game
Tag(s):

Ad-Hoc, Data Structures, Easy

Problem
Editorial
Analytics

Given $$2*N$$ pebbles of $$N$$ different colors, where there exists exactly $$2$$ pebbles of each color, you need to arrange these pebbles in some order on a table. You may consider the table as an infinite 2D plane.

The pebbles need to be placed under some restrictions :

  1. You can place a pebble of color $$X$$, at a coordinate $$(X,Y)$$ such that $$Y$$ is not equal to $$X$$, and there exist $$2$$ pebbles of color $$Y$$.

In short consider you place a pebble of color $$i$$ at co-ordinate $$(X,Y)$$. Here, it is necessary that $$(i=X)$$ , $$(i!=Y)$$ there exist some other pebbles of color equal to $$Y$$.

Now, you need to enclose this arrangement within a boundary , made by a ribbon. Considering that each unit of the ribbon costs $$M$$, you need to find the minimum cost in order to make a boundary which encloses any possible arrangement of the pebbles. The ribbon is sold only in units (not in further fractions).

Input Format:

First line consists of an integer $$T$$ denoting the number of test cases. The First line of each test case consists of two space separated integers denoting $$N$$ and $$M$$.

The next line consists of $$N$$ space separated integers, where the $$i^{th}$$ integer is $$A[i]$$, and denotes that we have been given exactly $$2$$ pebbles of color equal to $$A[i]$$. It is guaranteed that $$A[i]!=A[j]$$, if $$i!=j$$

Output Format:

Print the minimum cost as asked in the problem in a separate line for each test case.

Constraints:

$$ 1 \le T \le 50 $$

$$ 3 \le N \le 10^5 $$

$$ 1 \le M \le 10^5 $$

$$ 1 \le A[i] \le 10^6 $$ ; where $$1 \le i \le N$$

SAMPLE INPUT
1
3 5
1 2 3
SAMPLE OUTPUT
35
Explanation

An arrangement can be :
Pebbles of color 1: (1,2) , (1,3)
Pebbles of color 2: (2,1) , (2,3)
Pebbles of color 3: (3,1) , (3,2)
The length of ribbon required is= 6.828427125
The cost of ribbon is = 7*5=35 as we have to buy ribbon in units.
This arrangement's boundary covers all possible arrangements.

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: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup - Mirror Round

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications