An interesting game

Practice

2.7 (11 votes)

Algorithms

Greedy algorithms

Problem

61% Success 518 Attempts 50 Points 3s Time Limit 256MB Memory 1024 KB Max Code

You are given two arrays \(a_1, a_2,\ \dots, a_n\) and \(b_1, b_2,\ \dots, b_n \) where \(n\) is an even number. Alice and Bob are playing a game on these arrays. In each turn, Alice selects two unused numbers before numbers \(i \) and \(j\) such that \(1 \le i, j \le n\) and \(i \ne j\). Bob selects one of them and this number is denoted as \(x\) and adds \(b_x\) to his score. Alice takes the remaining one, that is denoted as \(y\), and adds \(a_y\) to his scores. Alice and Bob want to maximize their scores simultaneously. Your task is to determine the difference between their scores after the game. Totally, they have \(\frac{n}{2}\) turns. In other words, your task is to find the difference between Alice's and Bob's scores after all turns if both sides move optimally Input format The first line contains one integer \( t\ (1 ≤ t ≤ 1000) \) denoting the number of test cases. The first line of each test case contains one integer \(n\ (1 ≤  n ≤ 300000) \) denoting the length of the array. It is guaranteed that \(n\) is even. The second line of each test case contains \(n\) distinct integers \(a_1, a_2,\ \dots, a_n\) \((1 \le a_i \le 10^9)\) denoting the elements of array \(a\). The third line of each test case contains \(n\) distinct integers \(b_1, b_2,\ \dots, b_n\) \((1 \le b _i \le 10^9)\) denoting the elements of the array \(b\). The sum of \(n\) over all test cases does not exceed 300000. Output format For each test case, print a single integer denoting the difference between Alice's and Bob's scores after the game if both players move optimally

Sample Input

2
4
4 2 8 6
6 5 7 8
6
7 8 2 6 10 3
9 1 3 10 2 4

Sample Output

-4
8

Explanation

The moves of the first test case: Alice will choose integers 3 and 4. Bob must take 4 (it is optimally for him), hence Alice chooses 3. After the game, both of them have 8 scores. Alice will choose integers 1, 2. Bob must take 1 (it is optimally for him), hence Alice chooses 1. After the game, Alice has a score of 10 and Bob has a score of 14. Consequently, the answer is 10 - 14 = -4 . The moves of the second test case: Alice will choose integers 2, 3. Bob must take 3 (it is optimally for him), hence Alice chooses 2. After the game, Alice has 8 scores, Bob 3 scores. Alice will choose integers 5, 6. Bob must take 6 (it is optimally for him), hence Alice chooses 5. After the game, Alice has 18 scores, Bob 7 scores. Alice will choose integers 1, 4. Bob must take 4 (it is optimally for him), hence Alice chooses 1. After the game, Alice has 25 scores, Bob 17 scores. Consequently, the answer is 25 - 18 = 7 . It can be shown that both players move as optimally as they can and there can be no better outcome.

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Results

Custom Input

Run your code to see the output

Submissions