Pirates and Treasure
Time limit1sMemory limit256 MB
Two players alternately take chests, each valuing them differently; find the final difference when both play optimally.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Game theory, Math
- Solved
- No attempts yet
Problem
The pirates Alice and Bob recently found a huge amount of treasure on a treasure island. They found N treasure chests and agreed to split them fairly by taking turns picking one chest each. Since the value of each chest is hard to judge objectively, both of them wrote down their own valuation and shared it with each other. That is, the i-th chest is worth A[i] dollars to Alice and B[i] dollars to Bob.
To divide the chests, Alice and Bob take turns, starting with Alice, each taking one of the remaining chests. After one chest is taken, it is the other person's turn, and once all N chests have an owner, the two go their separate ways.
After all the chests are divided, let ScoreA be the total (by Alice's valuation) value of the chests Alice took, and ScoreB the total (by Bob's valuation) value of the chests Bob took. The two are honorable pirates who keep their promises, but they are also greedy, so Alice picks chests to maximize (ScoreA - ScoreB) and Bob picks chests to maximize (ScoreB - ScoreA).
The two always play their best when deciding which chest to take.
For example, suppose N = 3 and the three chests have the following values.
- Chest 1: A[1] = 10, B[1] = 5
- Chest 2: A[2] = 100, B[2] = 90
- Chest 3: A[3] = 2, B[3] = 0
If Alice takes chest 2 first, then Bob takes chest 1, and finally Alice takes chest 3, Alice gets 102 dollars and Bob gets 5 dollars. If Alice takes a chest other than chest 2 on her first turn (chest 1 or chest 3), Bob will take chest 2 on his turn, so in that case Alice gets 10+2 = 12 dollars and Bob gets 90 dollars. Therefore, if Alice plays her best, she must take chest 2 on her first turn.
Given the number of treasure chests N and the values each pirate assigns to the chests, write a program to find (ScoreA - ScoreB) when both players play their best to maximize their own goals.
Input
The first line gives the number of test cases T.
For each test case, the first line gives an integer N, the number of treasure chests.
The next N lines give the value of each chest, separated by a space. The first number is the value Alice assigns, and the second is the value Bob assigns.
Output
For each test case, print (ScoreA - ScoreB) when both players play the game with their best effort.
Constraints
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100,000
- 0 ≤ A[i], B[i] ≤ 100,000