Valentine Vex CodeChef Solution | CodeChef Problem Solution 2022

Valentine Vex CodeChef Solution | CodeChef Problem Solution 2022

Alice and Bob play a game on an array of N$N$ integers. They alternate moves, with Alice making the first move.

The rules are as follows:

1. On their first move, a player can pick any element in the array, add its value to their score, and then remove it from the array.
2. On a move that is not their first move, the player should pick an element with the opposite parity of the element chosen on their previous move, add its value to their score, and then remove it from the array.
3. If a player cannot make a move, either because the array is empty or it doesn't contain an element of the parity they need, the player skips their turn.
4. The game ends when both players are unable to move.

Note that the parity of an element chosen by a player depends only on the parity of their own previously chosen element — it does not depend on what their opponent last chose.

Determine the optimal score of Alice if both players play optimally, each attempting to maximize their own score. If there are multiple ways to obtain maximum score for themselves, the players will adopt a strategy that will maximize the score of their opponent whilst obtaining their maximum score themselves.

Note that it is not necessary to use all the elements in the array.

Input Format

• The first line of input will contain a single integer T$T$, denoting the number of test cases. Then the test cases follow.
• Each test case consists of two lines of input.
• The first line of each test case contains one integer N$N$ — the size of the array A$A$
• The second line of each test case contains N$N$ space-separated integers, denoting the array elements.

Output Format

For each test case, output on a new line the optimal score achieved by Alice.

Constraints

• 1≤T≤2⋅104$1\le T\le 2\cdot {10}^4$
• 2≤N≤105$2\le N\le {10}^5$
• 1≤Ai≤106$1\le Ai\le {10}^6$
• Sum of N$N$ across all test cases won't exceed 2⋅105$2\cdot {10}^5$

Sample Input 1 

3
4
1 2 3 4
3
45 10 53
6
7 5 2 2 6 2

Sample Output 1 

5
55
15

Explanation

Test case 1$1$: Under optimal play, Alice's maximum score is 5$5$. One sequence of moves leading to this score is:

Solution Click Below:- 

• On her first move, Alice picks 4$4$.
• On his first move, Bob picks 3$3$.
• On her second move, Alice must choose an odd number, since she previously picked an even number. So, Alice's only choice is to pick 1$1$.
• On his second move, Bob picks 2$2$, since he must choose an even number and it is the only one left.

Alice's score is thus 4+1=5$4+1=5$. Note that this is not the only optimal strategy — however, any other strategy where both players play optimally will still lead to Alice having a score of 5$5$.

Test case 2$2$: Alice's strategy is as follows:

• On her first move, Alice picks 10$10$.
• On his first move, Bob picks 53$53$.
• Finally, Alice picks 45$45$, ending up with a score of 10+45=55$10+45=55$.
• 
  
• Note that if Alice picks either 53$53$ or 45$45$ on her first move, Bob will pick 10$10$ on his move. This leaves Alice unable to make a move, so she skips her turn and Bob picks the remaining number, leaving Alice with a score strictly smaller than 55$55$.

Chef and Chapters CodeChef Solution | CodeChef Problem Solution 2022

Presents for Cheffina CodeChef Solution | CodeChef Problem Solution 2022

Chef and Bird farm CodeChef Solution | CodeChef Problem Solution 2022

Valentine Vex CodeChef Solution | CodeChef Problem Solution 2022

Buying Sweets CodeChef Solution | CodeChef Problem Solution 2022

Reduce to 1 CodeChef Solution | CodeChef Problem Solution 2022

Three Arrays CodeChef Solution | CodeChef Problem Solution 2022

Test case 3$3$: Alice picks 6,7,$6,7,$ and 2$2$ for a score of 15$15$, while Bob picks 2,5,$2,5,$ and 2$2$ for a score of 9$9$. Note that Bob can also achieve a score of 9$9$ by picking 7$7$ and 2$2$ and then skipping his third move, but he won't do this because it would lead to Alice only reaching a score of 13$13$ — as mentioned earlier, a player attempts to maximize their own score, and then maximize their opponent's score.

Join Now for Solution:-