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.
TIME COMPLEXITY:
O(N) for each test case.
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution