PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: S.Manuj Nanthan
Tester: Felipe Mota, Aryan
Editorialist: Pratiyush Mishra
DIFFICULTY:
2429
PREREQUISITES:
None
PROBLEM:
Alice and Bob play a game on an array of N integers. They alternate moves, with Alice making the first move.
The rules are as follows:
- 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.
- 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.
- 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.
- 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.
EXPLANATION:
This game can be played in four ways:
- Both Alice and Bob picks an even number.
- Both Alice and Bob picks an odd number.
- Alice picks an even number while Bob picks an odd number.
- Alice picks an odd number while Bob picks an even number.
In either of the four ways, the game would then proceed the same for both, i.e picking of alternating even-odd numbers in decreasing order.
Since Alice makes the first move, so she would select either odd or even depending upon which would maximise her final score. For Alice’s selection, Bob will then have two options to either select even or odd depending upon which would maximise his final score.
Assuming a function called f(mask) which gives the pair of score of Alice and Bob with respect to the given mask, whose first bit represents the choice of Bob and second bit represents the choice of Alice. Here mask is define as follows:
mask = 0 => Both Alice and Bob picks even number
mask = 1 => Alice picks an even number while Bob picks an odd number.
mask = 2 => Alice picks an odd number while Bob picks an even number.
mask = 3 => Both Alice and Bob picks odd number.
Now for a particular choice of Alice, her final score would depend on the choice of Bob's choice who aims to maximise his own score.
- Alice choses even initially, then her score would be
- f(0) if Bob score’s maximises if he also choses even initially
- f(1) if Bob score’s maximises if he choses odd initially
- max(f(0),f(1)) if Bob’s score is the same in both of his choices.
- Alice choses odd initially, then her score would be
- f(2) if Bob score’s maximises if he choses even initially
- f(3) if Bob score’s maximises if he also choses odd initially.
- max(f(2),f(3)) if Bob’s score is the same in both of his choices.
Out of these two cases of Alice's choice, her score would be the maximum out of the two.
TIME COMPLEXITY:
O(NlogN) for each test case.
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution