MAXORMIN Editorial

editorial
, , ,
#1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Jakub Safin, Satyam
Editorialist: Pratiyush Mishra

DIFFICULTY:

1313

PREREQUISITES:

Bitwise Operations

PROBLEM:

Alice and Bob are ready to play a new game. Both the players take alternate turns. Alice starts first.

There are N binary numbers written on a blackboard.

  • Alice, in her turn, erases any 2 numbers from the blackboard and writes the bitwise OR of those 2 numbers on the blackboard.
  • Bob, in his turn, erases any 2 numbers from the blackboard and writes the bitwise AND of those 2 numbers on the blackboard.

Note that, after each move, the count of numbers written on the blackboard reduces by 1.

Both players play until a single number remains on the blackboard. Alice wants to maximise the remaining number while Bob wants to minimise the remaining number. Find the remaining number if both the players play optimally.

EXPLANATION:

Here we count the number of 1 and 0 written on the blackboard and store it in variables ones and zeroes respectively.
Now we observe that in one move Alice can take a 1 and 0 and remove the 0 from the board by taking bitwise OR while Bob can take a 0 and a 1 and remove the 1 by taking bitwise AND, provided both 1 and 0 exists.
In the end if only 1s exists then the last remaining would also be 1 only and same for 0.
Thus we just need to check the initial number of 1s and 0s and our answer would be based on whichever one is greater.

answer = \begin{cases} 1 , \; if \; ones \geq zeroes \\ 0 \;if \; ones < zeroes \end{cases}

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

#2

Bonus problem. I am not able to come up with solution:
what if instead of 0<=A[i]<=1 we have 0<=A[i]<=10^9 .
How do we get final answer?
Any help is appreciated!!

#3

I feel (not able to prove it though) that u wud choose the largest and smallest number.

If u think about the numbers in binary format, then the largest number will have a 1 to the leftmost and the smallest number wud have a 1 to the rightmost. So if we take an OR, we are preserving all the 1s of the largest number and possibly add some from the smallest one. Similarly while taking AND, u r eating up the 1s of the largest number since the smallest contains 0s in those leftmost places. So that way we can always keep a set and keep picking the smallest and largest number for the operations.

I think this might work. But if this fails due to some other contradictory case, we will need to use DP i guess. Since DP is the only way to make this choice in a smart manner to always return the maximum/minimum result.

1 Like
#4

how is the answer of
2
1 1
is 1 shouldn’t it be 0 as 1^1 = 0

#5

#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–){
bool flag=true;
int n;
cin>>n;
int arr[n];
map<int,int>m;
for(int i=0;i<n;i++){
cin>>arr[i];
m[arr[i]]+=1;
}
while(m[0]>0 && m[1]>0){
if(flag==true){
m[0]–;
if(m[0]==0){
m.erase(0);
}
flag=false;
}
else{
m[1]–;
if(m[1]==0){
m.erase(1);
}
flag=true;
}
}
while(m[0]>1){
m[0]=m[0]-1;
}
while(m[1]>1){
m[1]=m[1]-1;
}
map<int,int>::iterator x=m.begin();
while(x!=m.end()){
if(x->second==1){
cout<first<<endl;
}
x++;
}

}

}