[Solution] Valentine Vex solution codechef

Valentine Vex solution codechef – Alice and Bob play a game on an array of NN integers. They alternate moves, with Alice making the first move.

[Solution] Valentine Vex solution codechef

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 TT, 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 NN — the size of the array AA
  • The second line of each test case contains NN space-separated integers, denoting the array elements.

Output Format

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

[Solution] Valentine Vex solution codechef

  • 1T21041≤T≤2⋅104
  • 2N1052≤N≤105
  • 1Ai1061≤Ai≤106
  • Sum of NN across all test cases won’t exceed 21052⋅105

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

Valentine Vex solution codechef Explanation

Test case 11: Under optimal play, Alice’s maximum score is 55. One sequence of moves leading to this score is:

  • On her first move, Alice picks 44.
  • On his first move, Bob picks 33.
  • 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 11.
  • On his second move, Bob picks 22, since he must choose an even number and it is the only one left.

Alice’s score is thus 4+1=54+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 55.

Test case 22: Alice’s strategy is as follows:

  • On her first move, Alice picks 1010.
  • On his first move, Bob picks 5353.
  • Finally, Alice picks 4545, ending up with a score of 10+45=5510+45=55.

Note that if Alice picks either 5353 or 4545 on her first move, Bob will pick 1010 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 5555.

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

For Solution

Click here

Leave a Comment