PROBLEM LINK:
Setter: Md. Reyad Hossain
Tester: Alexander Morozov
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
PROBLEM:
We are given an sequence of size N with entries A_1, A_2,...., A_N . In one operation we can take two integers i and j where 1 \leq i \lt j \leq N and a non-negative integer p and do the following: change A_i to A_i \oplus 2^p , A_j to A_j \oplus 2^p where \oplus denotes the bitwise xor operation. We need to get the lexicographically smallest sequence after applying this operation exactly X times. Here N \geq 2.
QUICK EXPLANATION:
Iterate i from 1 to N-1 , try to minimize the value of A_i . This can be done as follows:
For each A_i, traverse from the most significant bit to least signicant bit and do the following:
- If the current bit b is set to 1 , then search for the nearest next index j from i where the bit b is set to 1 for A_j . (if we don’t find any such j, then take j=N) . Now take p=b, i and j and perform the operation mentioned in the problem. Also keep track of number of operations performed.
If at any stage, the total number of operatons equal to X, we stop the above process and output the updated sequence. If we still have some number of operations Y left to do, we do the following on this current updated sequence:
-
If N=2 and Y is odd, then perform the operation once on i=N-1, j = N and p=0 and output the sequence.
-
Else output the current sequence as the answer.
EXPLANATION:
First let’s understand what is the meaning of the operation. We take two integers i and j, where 1 \leq i \lt j \leq N and a non-negative integer p and apply A_i=A_i \oplus 2^p and A_j = A_j \oplus 2^p. This means that we are toggling the p^{th} position bit of A_i and A_j. (if the bit is set, we unset it and vice-versa) .
Since we need to get the lexicographically smallest sequence after N operations, we need to first try and minimize A_1, then A_2 , then A_3, ..... then A_{N} and stop whenever we run out of operations.
Let’s think about this problem in this manner: Suppose we have minimized A_1, A_2, ... , A_{i-1} to their maximum extents (i.e, made all A_1, A_2, A_3, ..., A_{i-1} = 0) and now we are trying to minimize A_i . (Let i \lt N. We deal with the case of i=N later). What can we do? Now that we are trying to minimize A_i, we try to minimize it from the most significant bit (MSB) to the least significant bit (LSB) since unsetting the bits with high value will reduce the value of A_i to a great extent . Now for the main question, if a bit b while traversing in the order from MSB to LSB is set to 1, we want to make it to 0, so we try to apply the operation for the current i and p=b, but what is the value of j that we should take?
Answer
-
We must try to take j \gt i, since it is always better than taking j<i since in the latter case the value of A_j where j \lt i is already minimized.
-
Now for the j we are going to take, it’s optimal to take j such that A_j has bit b set to 1 if we have one. (since we can unset the bit b for A_i and A_j) . Also, among all such possible options for j, its better to take such j which is nearer to i since we are aiming for the lexicographically smallest sequence.
-
If we don’t have for any j \gt i, the bit b of A_j set to 1, the only better option to make the bit b of A_j unset is to take j=N.
Thererfore, we try to perform operations in this manner till we run out of operations or reach A_N. If we run out of operations, we immediately output the resultant sequence. Otherwise we must have reached A_N and have some Y \gt 0 operations remaining. Since each number can have atmost \log(10^9) bits, we must have performed atmost (N-1) \cdot \log(10^9) operations till now. We want to preserve this current sequence if possible since the current sequence is the lexicographically smallest sequence. Consider the following cases:
-
N=2 \ \ and \ \ Y \ is \ odd
We can perform the operation (p=0, i=N-1, j=N) Y times so that this operaton has its effect for only one time since performing the same operation twice is equivalent to not performing the operation at all. -
N \ge 3 \ \ and \ \ Y = 1
In this case, we can show that we can preserve the lexicographically smallest sequence. The main idea is to perform some extra dummy operation before starting our main approach to the solution. Suppose initially before applying any operation we have an array A of length N. Now suppose we have found three indices 1 \le i \lt j \lt k \le N which have their bits set at position loc . Now before proceeding our main approach, apply the following operations
(p =loc, i, k), (p=loc, j, k) . Now observe that instead of performing 1 operation to unset bits at values at two indices i and j as described in the main approach , we have performed 2 operations and thus performed an extra dummy operation . Now suppose we didn’t find any such i, j, k, then we are sure to find out two indices 1 \le i,j \le N where i has the bit set at position loc and j is the smallest index which has the bit unset at position loc . Now before proceeding our main approach, apply the following operation (p=loc, i, j) . This doesn’t effect the result from our main approach and thus we have performed one extra dummy operation to preserve the lexicographically smallest sequence. -
Else we can show that in this case also we can preserve the lexicographically smallest sequence. First if Y is even, we can choose any valid operation and perform that same operation Y times, so that there is effectively no change at all with these Y operations (since Y is even). If Y is odd, we can choose any valid operation and perform that same operations Y-3 times. Since Y-3 is even, there will be effectively no change with these operations. Now we need to still perform 3 operations. We can perform the operation in the following way: (p=0, i=N-1, j=N), (p=0,i=N-2, j=N-1) and (p=0,i=N-2, j=N). If we observe carefully, the bit 0 of i=N-2, i=N-1, i=N are toggled 2 times each which is effectively equivalent to not performing the operation at all.
TIME COMPLEXITY:
O(N \cdot \log(10^9)) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int N, X;
cin >> N >> X;
vector<int> a(N);
vector<vector<int>> bit_locs(31);
vector<int> ptr(31, 0);
for (int i = 0; i < N; i++)
cin >> a[i];
for (int i = 0; i < N; i++)
{
for (int j = 30; j >= 0; j--)
{
if ((1 << j) & a[i])
bit_locs[j].push_back(i);
}
}
int operations = 0;
for (int i = 0; i < N - 1; i++)
{
if (operations == X)
break;
for (int j = 30; j >= 0; j--)
{
if (operations == X)
break;
if ((1 << j) & a[i]) // now find nearest bit j which is set if possible
{
if (ptr[j] + 1 < (int)bit_locs[j].size())
{
a[i] ^= (1 << j);
a[bit_locs[j][ptr[j] + 1]] ^= (1 << j);
ptr[j] += 2;
}
else
{
a[i] ^= (1 << j);
a[N - 1] ^= (1 << j);
}
operations++;
}
}
}
int Y = X - operations;
if (N == 2 && Y % 2 == 1)
{
a[N - 1] ^= 1;
a[N - 2] ^= 1;
}
for (int i = 0; i < N; i++)
cout << a[i] << " ";
cout << endl;
}
}
VIDEO EDITORIAL:
Please comment below if you have any questions, alternate solutions, or suggestions.
