All Tracks Algorithms Graphs Depth First Search Problem

Reduction Game
Tag(s):

Algorithms, Depth First Search, Graphs, Medium

Problem
Editorial
Analytics

You are given an array \(A\) consisting of \(N\) distinct integers. If the size of the array is greater than one, then you can perform the following operations any number of times:

  • Select two integers \(A_i\) and \(A_j\) such that \(CountOnes(A_i \oplus A_j) = 1\) and delete either \(A_i\) or \(A_j\) from the array. This operation costs \(C_1\).

  • Select two integers \(A_i\) and \(A_j\) such that \(CountOnes(A_i \oplus A_j) \gt 1\) and delete either \(A_i\) or \(A_j\) from the array. This operation costs \(C_2\).

Here, \(CountOnes(X)\) returns the number of \(1s\) available in the binary representation of integer \(X\). Determine the minimum cost to reduce the size of the array to \(1\).

Input format

  • First line: \(T\) denoting the number of test cases
  • For each test case:
    • First line: \(N\)
    • Second line: Two space-separated integers \(C_1\) and \(C_2\)
    • Third line: \(N\) space-separated integers denoting the array \(A\)

Output format

For each test case, print a single integer in a separate line as described in the problem statement

Constraints

\(1 \le T \le 20\)

\(1\le N\le 10^4\)

\(1 \le C_1,C_2,A_i \le 10^9\)

Subtasks

  • For 10 points: \(1 \le N \le 10\)
  • For 90 points: Implement the original constraints
SAMPLE INPUT
1
4
50 100
1 2 3 4
SAMPLE OUTPUT
200
Explanation

We take 1 and 3 and delete 1 with cost 50. Next we take 3 and 2 and delete 2 with cost 50. Last, we take 3 and 4 and delete 4 with cost 100.

So total cost = 50+50+100 = 200

Time Limit: 2.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), TypeScript, 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #7

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?