VALVEX Editorial

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:

  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.

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

3 Likes

my solution has same idea and it passes ( 3 by 5 test cases)
can someone help point out which case my solution fails ?
solution link : Solution: 63840684 | CodeChef

After calculating the score for all the 4 mask , u need to take the max of mask [0,1] and mask[2,3] but u took the min and it should be max (i still doesn’t know why but yaa ok).

Updated Code :

ll aa = -1, bb = -1;
if(opa.S == opb.S) aa = max(aa,max(opa.F, opb.F));
else if(opa.S > opb.S) aa = max(aa,opa.F);
else aa = max(aa,opb.F);
if(opc.S == opd.S) bb = max(bb,max(opc.F, opd.F));
else if(opc.S > opd.S) bb = max(aa,opc.F);
else bb = max(aa,opd.F);

My Code Failed On 5th TestCase
I checked Someone Ac code it gives ans 15 to testcase [ 6 , 9 , 9 ,3 ]
but my ans is 18
as we can see Alice= 9 6 3 = 18 and Bob=9 =>which is always optimal
another is Alice= 6 9 =15 and BOB=9
Can Someone Explain me why it is not correct : (

1 Like

Alice & Bob both are playing optimally .
& since Alice starts 1st soo , if Alice takes 9 at first , then Bob will take 6 after that Alice cannot make move . So , in that case Alice will lose the game .
But if Alice takes 6 at 1st move then BOB have to take (9 , 9 , 3) any of the odd numbers then Bob will take 9 because it’s maximum value present .
after that Alice will take 9 then Bob cannot make any further move .
So , the answer is 6 +9 = 15 .

2 Likes

bro but in question said ,
. 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.
So BOB maximum score is always 9 Because of that bob will help to Alice to maximize their score
and hence alice score is 18 instead of 15 because in both cases bob maximum score will remain same.
Thanks for your reply

2 Likes

I did the exact same thing by creating all the 4 cases but still I am getting wrong answer. Can someone please help me out.

This is my code:

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define test int t;cin>>t;while(t–)

signed main(){

test{

    int n;

    cin>>n;

    vector<int>a(n);

    for(int i=0;i<n;i++){

        cin>>a[i];

    }

    vector<int>even;

    vector<int>odd;

    for(int i=0;i<n;i++){

        if(a[i]%2==0){

            even.push_back(a[i]);

        }

        else{

            odd.push_back(a[i]);

        }

    }

    sort(even.begin(),even.end(),greater<int>());

    sort(odd.begin(),odd.end(),greater<int>());

    // Case 1 even even

    int i=0,j=0,missed_chances=0;

    int alice1=0,bob1=0;

    int alice_chance=1,bob_chance=1;

    while(i<even.size() ||j<odd.size()){

        if(i<even.size()&&alice_chance%2==1){

            alice1+=even[i];

            i++;

            alice_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            alice_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(i<even.size()&&bob_chance%2==1){

            bob1+=even[i];

            i++;

            bob_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            bob_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(j<odd.size()&&alice_chance%2==0){

            alice1+=odd[j];

            j++;

            alice_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            alice_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(j<odd.size()&& bob_chance%2==0){

            bob1+=odd[j];

            j++;

            bob_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            bob_chance++;

        }

        if(missed_chances>=2){

            break;

        }

       

    }

    // Case 2 even odd

    i=0,j=0,missed_chances=0;

    int alice2=0,bob2=0;

    alice_chance=1,bob_chance=1;

    while(i<even.size() ||j<odd.size()){

        if(i<even.size()&&alice_chance%2==1){

            alice2+=even[i];

            i++;

            alice_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            alice_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(j<odd.size()&& bob_chance%2==1){

            bob2+=odd[j];

            j++;

            bob_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            bob_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(j<odd.size()&&alice_chance%2==0){

            alice2+=odd[j];

            j++;

            alice_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            alice_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(i<even.size()&&bob_chance%2==0){

            bob2+=even[i];

            i++;

            bob_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            bob_chance++;

        }

        if(missed_chances>=2){

            break;

        }

    }

    //Case 3 odd even

    i=0,j=0,missed_chances=0;

    int alice3=0,bob3=0;

    alice_chance=1,bob_chance=1;

    while(i<even.size() ||j<odd.size()){

        if(j<odd.size()&&alice_chance%2==1){

            alice3+=odd[j];

            j++;

            alice_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            alice_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(i<even.size()&&bob_chance%2==1){

            bob3+=even[i];

            i++;

            bob_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            bob_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(i<even.size()&&alice_chance%2==0){

            alice3+=even[i];

            i++;

            alice_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            alice_chance++;

        }

        if(missed_chances>=2){

            break;

        }

                   

        if(j<odd.size()&& bob_chance%2==0){

            bob3+=odd[j];

            j++;

            bob_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            bob_chance++;

        }

        if(missed_chances>=2){

            break;

        }

       

    }

    //Case 4 odd odd

    i=0,j=0,missed_chances=0;

    int alice4=0,bob4=0;

    alice_chance=1,bob_chance=1;

    while(i<even.size() ||j<odd.size()){

        if(j<odd.size()&&alice_chance%2==1){

            alice4+=odd[j];

            j++;

            alice_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            alice_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(j<odd.size()&& bob_chance%2==1){

            bob4+=odd[j];

            j++;

            bob_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            bob_chance++;

        }

        if(missed_chances>=2){

            break;

        }

        if(i<even.size()&&alice_chance%2==0){

            alice4+=even[i];

            i++;

            alice_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            alice_chance++;

        }

        if(missed_chances>=2){

            break;

        }

                   

        if(i<even.size()&&bob_chance%2==0){

            bob4+=even[i];

            i++;

            bob_chance++;

            missed_chances=0;

        }

        else{

            missed_chances++;

            bob_chance++;

        }

        if(missed_chances>=2){

            break;

        }

       

    }

    int even_alice;

    int odd_alice;

    if(bob1==bob2){

        even_alice=max(alice1,alice2);

    }

    else if(bob1>bob2){

        even_alice=alice1;

    }

    else if(bob1<bob2){

        even_alice=alice2;

    }

    if(bob3==bob4){

        odd_alice=max(alice3,alice4);

    }

    else if(bob3>bob4){

        odd_alice=alice3;

    }

    else if(bob3<bob4){

        odd_alice=alice4;

    }

    cout<<max(even_alice,odd_alice)<<endl;

}

return 0;

}

Thanks cricket_99
Understood finally : )

If Alice chooses 9 on her first move, Bob will go ahead with 6 rather than 9 because he wants to maximize his own score. If he chooses 6, his score will 6+9 = 15 and if he chooses 9, his score will be 9. Hence, he will choose 6+9 and then Alice’s score will become 9.
On the other hand, if Alice chooses 6 on her first move, Bob will have to go with 9 (the only option left with him). In this way, Alice’s final score will be 6+9 = 15 while Bob’s score will be 9.