All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

When the Integers got upset!
/

Bit manipulation, Bitmask, Dynamic Programming

Problem
Editorial
Analytics

Puchi was crossing a river by jumping over stepping stones, carrying a bag containing N integers. Our Monk saw him from the banks and shouted out to him. Shaken by the sudden shout, Puchi dropped the bag in the river and all the integers got wet! This upset the integers.
There are N stepping stones available ahead. Puchi wants to dry these integers on these stones, such that each stone contains a single integer. The upset value of the i'th integer Ai (after rearrangement of the integers) is (Ai ^ Ai-1 ^ Ai-2) times Pi for i ≥ 2, and 0 otherwise. (where '^' is the bit wise XOR operator). Here, i represents the position of the said integer.

Puchi asks our Monk to find an order of arranging the numbers on the stones, such that sum of upset values is minimized. Help our Monk find the order, given the arrays A and P .
Input:
First line contains T. T test cases follow.
First line of each test case contains an integer N.
Second line of each test case contains N integers, forming the array A.
Third line of each test case contains N integers, forming the array P.

Output:
Print the answer to each test case in a new line.

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 12
0 ≤ Ai ,Pi ≤ 200

SAMPLE INPUT
2
4
2 5 4 6
1 1 1 1
5
13 3 9 4 2
1 1 1 1 1
SAMPLE OUTPUT
1
14
Explanation

For the first test case, optimal ordering can be 5 6 2 4. The upset values will be 0 ,0 ,(5^6^2)x1 , (6^2^4)x1 which amounts to 0+0+1+0=1.
For the second test case, optimal ordering can be 3 2 9 13 4. The upset values will be 0 ,0 ,(3^2^9)x1 ,(2^9^13)x1 ,(9^13^4)x1 which amounts to 8+6+0=14

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?