DCP-475: Bunty's Xor Game Back to All Problems

Hard Divide and Conquer > Dynamic Programming

As you know, **Bunty** loves playing with numbers. He is now playing a game with his sister. Initially there is an array of N integers. They play the game in turns. **Bunty gives the first move**. In each move, one can choose two numbers from the array and score of this turn is the xor of the two numbers. After each turn, player removes the selected two integers from the array. The game continues until the array is empty. Now Bunty wants to know , what is the maximum score he can obtain. Note: Both of them play optimally well i.e Bunty's sister always plays in such a way that will make score of Bunty lesser and Bunty tries to maximize his score as much as possible. The Final Score of Bunty is the sum of all round played by Bunty Input: ------ Input starts with an integer **T (1<=20)**, denoting the number of test cases. Each case contains an integer **N ( 2≤ N ≤ 16)** denoting the number of elements of array A. N will be always even. Then in the next line there are N non-negative integers **(0 <= Ai <= 10^9)** Output: ------- For every test case, output the maximum score Bunty can obtain if both play optimally. Sample Input ------------ 1 4 1 2 4 3 Sample Output ------------- 7

Problem Setter:

Kazi Sohan

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 2.00
Go 2.00
Java 4.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 4.00
Python3 4.00
Ruby 2.00
VB.Net 2.00

Problem Stats




# User Language Timing
01 Robbinb1993 Cpp14 0.29s
02 Morass Cpp14 0.51s
03 amin21 Cpp 0.51s
04 kzvd4729 Cpp14 0.54s
05 mahbubcseju Cpp 0.55s
06 ovis96 Cpp14 0.57s
07 Hasinur_ Cpp 0.59s
08 Tahmid Cpp14 0.74s
09 akazad_cse13_ruet Cpp 0.79s
10 Trumen Cpp 0.85s
11 ksohan Cpp 0.93s
12 Dayamoy Cpp14 0.95s
13 njrafi Cpp 0.97s
14 CLown1331 Cpp 1.04s
15 Mr_adnan Cpp 1.20s
16 PKP_007 Cpp 1.30s
17 racsosabe Cpp 1.31s
18 showmic Cpp14 1.34s
19 AlaminJust Cpp 1.81s
20 Zeronfinity Cpp 1.95s

Your feedback is our precious!

Or call +88 02 9853138 for support