Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

### Utsavcc's blog

By Utsavcc, 6 weeks ago,

Given an array of elements Ai (<=1e9) of length N (<=1e5), and another array named 'operands' of size K (<=4), You can do the following operations as many times as desired: Select any element in original array and XOR it with any element in 'operands' array. Minimize the Maximum difference between any pairs of the array.

• +4

 » 6 weeks ago, # | ← Rev. 3 →   -10 it's a little "sus" on your avatar
 » 6 weeks ago, # |   0 I don't understand what does K do here?
•  » » 6 weeks ago, # ^ |   0 Updated the statement, let me know if the problem is intuitive.
 » 6 weeks ago, # |   0 One idea I could think of immediately:Pivot $A_1$. Perform $16$ different cases, with each case having $A_1$ xor-ing with every element in a subset of operand array (empty subset means keeping $A_1$ as-is), we'll call the new value $A_1'$.For each case, try to make other elements as close to $A_1'$ as possible. As one can guess, any other element also has $16$ possibilities each.This solution has $\mathcal{O}(n \cdot 4^k)$ complexity.
•  » » 6 weeks ago, # ^ |   0 Considering whatever you explained, consider this: How about for every subset of operands, we XOR the subset XOR value with each element of the array, sort those 16 possibilities and store it in a matrix[N][16]. Now the problem statement just changed to selecting one element from each row and maintaining minimum difference between the maximum chosen and the minimum chosen value. Isn't this a famous question we've seen somewhere?
•  » » » 6 weeks ago, # ^ |   0 Yes, here we can enumerate the minimum and then use O(2^k·n) to solve. When an element no longer qualifies for the minimum value, we replace it with an element in the array that is just larger than it.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 Making each element as close to a1 as possible doesn't guarantee the greatest gap is the least, right? ​For example, a2 = (a1-1 or a1+5). a3 = (a1+5 or a1+7).​ You would choose "a1-1" versus "a1+5" with a difference of 6.​ The correct choice is "a1+5" and "a1+5", the difference is 5.And you can't handle the case if you have two closest values at the same time.
•  » » » 6 weeks ago, # ^ |   0 I see. My bad there.
 » 6 weeks ago, # |   0 Nice pic bro
 » 6 weeks ago, # | ← Rev. 2 →   +1 There are in total 16 possible masks for the each element of the array. Generate those 16 masks and XOR each element of the array with it and sort all values and store it in a N x 16 matrix. Now you have a matrix with each row sorted, apply priority queue and keep N-pointers for each row and iterate through all elements column wise. Here's the code: #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include using namespace std; #define int long long using namespace std; // Basically finding minimum difference between maximum and minimum element if we choose one element from each row int minDifference(vector>& matrix) { int n = matrix.size(); priority_queue>, vector>>, greater>>> minHeap; int currentMax = numeric_limits::min(); for (int i = 0; i < n; i++) { minHeap.push({matrix[i][0], {i, 0}}); currentMax = max(currentMax, matrix[i][0]); } int minDiff = numeric_limits::max(); while (true) { auto minElem = minHeap.top(); minHeap.pop(); int value = minElem.first; int row = minElem.second.first; int col = minElem.second.second; minDiff = min(minDiff, currentMax - value); if (col + 1 < matrix[row].size()) { int nextElem = matrix[row][col + 1]; minHeap.push({nextElem, {row, col + 1}}); currentMax = max(currentMax, nextElem); } else { break; } } return minDiff; } int solve(int n, int q, vector& arr, vector& qrr) { vectorpos; for(int i=0;i<(1<0) { mask^=qrr[j]; } } pos.push_back(mask); } vector>brr; for(int i=0;ix; for(auto j:pos) { x.push_back(arr[i]^j); } sort(x.begin(),x.end()); brr.push_back(x); } return minDifference(brr); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while(t--) { int N, Q; cin >> N >> Q; vector arr(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } vector qrr(Q); for (int i = 0; i < Q; i++) { cin>> qrr[i]; } int ans = solve(N, Q, arr, qrr); cout<
 » 6 weeks ago, # | ← Rev. 2 →   0 We have 16 possibilities we can do on each array value, for each apply it on A1, let us note it as A1'. Now we center all others element around A1', by doing binary search, let's find the minimum k, such as A1' — k <= Ai' <= A1 + k, and the answer will be minimum of maxAi' — minAi' among all possibility. The complexity is O(nlogn). Each step of the binary will be O(n) because for each i, we will verify only among 16 cases, if at least one is in the interval.