HXOR - Editorial

PROBLEM LINK:

Practice
Div1
Div2

Setter: Md. Reyad Hossain
Tester: Alexander Morozov
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Bitwise XOR

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.

11 Likes

thanks, nice question

very good question and very high Plag also CodeChef do something

22 Likes

What should be the output of this?
i/p: 1
3 2
2 2 3
o/p: 0 1 2 (obtained on accepted solutions)
But we can obtain (0,0,3) here
Step-1: Choose i=1,j=3,p=1
new array obtained (0,2,1)
Step-2: Choose i=2,j=3,p=1
new array obtained (0,0,3)
(0,0,3) is lexicographically smaller than (0,1,2)
Or we are not allowed to make changes to the initial array and a totally new one is to be obtained?

5 Likes

0 0 3 is right ans…it should not accept 0 1 2 as an ans.

2 Likes

i think they should not consider p=0 ,when we reach the An and still have some operations left to do.as mentioned in the explanation

  • Y=1
    If Y=1Y=1, we must perform 1 more operation compulsorily. The best way to do this to keep the resultant sequence lexicographically as small as possible is to take (p=0, i=N-1, j=N)(p=0,i=N−1,j=N) and apply the operation.
  • N=2 \ \ and \ \ Y \ is \ oddN=2 and Y is odd
    We can perform the operation (p=0, i=N-1, j=N)(p=0,i=N−1,j=N) YY 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.

Can anyone please tell me why my code is giving TLE for one case.
The complexity is O(32*N). Code - Here

change unordered_map to ordered map

Can somebody help me solve this issue, please…

my code

Hi. Yes, you are right. Thanks for mentioning this. I have updated the editorial. When N \ge 3 and Y = 1, we can preserve the lexicographically smallest sequence and I have written the proof for it.

3 Likes

very weak testing such that some wrong solution or runtime error in same cases codes successfully accepted

for Input:
1
3 3
2 4 6
The output according to this editorial and my understanding:
0 1 1
But we can achieve 0 0 0 if we do:
operation1:
(p=1,i=1,j=3): 0 6 6
operation2:
(p=2,i=2,j=3): 0 2 2
operation3:
(p=1,i=2,j=3): 0 0 0

The answer will be 0 0 0 . Please go through the updated editorial. The case where N \ge 3 and Y=1 must preserve the lexicographically smallest sequence. Also, your operation 1 must be (p=1, i=1, j=2) .

During contest, I tried the last step even if n > 2 which caused WA. Now, adding this condition made the solution AC.

Anyway, my solution is O(n^2 logn) and is still AC.

https://www.codechef.com/viewsolution/40444884

Try using bitwise left shift operators “<<” instead of “**” to calculate 2^p. Bitwise calculations are faster than normal arithmetical calculations.

Can anyone suggest me a testcase for which my program is showing WA ?
Link for my solution: CodeChef: Practical coding for everyone

Thanks in adVance to the responder…
And remember to SavE watEr…

Tried but the problem still gives same TLE… :face_with_thermometer:

use this print(" ".join(map(str, arr))
instead of print(*arr)

Try to segregate your problem into parts. What I have done during the contest and noted that whenever X is greater than N, the minimum sequence will be the answer. Whenever N is greater you need to get the series. The task that you are getting TLE now, has bugged me off for 3 days straight, after which I segregated the tasks and got AC.
So, whenever X is greater than N you can just print the minimum series. But how to get it?
Well, you just need to XOR every element in the list/array/vector till the last element and store the final value in the last index and making all other values to be zero.
Example:
1
6 7
14 1 10 12 6 5

Normally:
(14) 1 (10) 12 6 5
(6) 1 2 (12) 6 5<–1
(2) 1 (2) 8 6 5<–2
0 (1) 0 8 6 (5)<–3
0 0 0 (8) 6 (4)<–4
0 0 0 0 (6) (12)<–5
0 0 0 0 (2) (8)<–6
0 0 0 0 0 10<–7

But if you XOR all the elements:
^ is XOR
14^1^10^12^6^5=10 Which is the last value of the list/array/vector and by making the previous elements 0, you will get the minimum sequence.
You can take reference from my solution.

My Solution

1 Like

@joy_321
Write a Condition as follow:
if i == n-2 and j == n-1 and arr[i] == 0:
then if n == 2 and x%2 == 1:
… … .(nested if)arr[i] ^= 1
… … .(nested if)arr[j] ^= 1
… … .break