XOR - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

At first we have to sort the array A[].

Next let’s do some basic observations. Consider the highest bit. Let its index be H. Then, there are CNT0 numbers that have zero H-th bit and CNT1 numbers that have unit H-th bit (CNT0+CNT1=N). Then C0=CNT0(CNT0*-1)/2+CNT1*(CNT1-1)/2 pairwise XORs will have zero H-th bit and *C1=CNT0CNT1 - unit H-th bit. If K<=C0 then the first K pairwise XORs will have zero in H-th bit. Otherwise all C0 pairwise XORs with zero in H-th bit should be added to the resulting array and we should find K-C0 pairwise XORs that has unit H-th bit.

Now what is going on in the general situation.
There are two possible scenarios when we consider the h-th bit (0<=h<=H).

  1. All highest bits from h+1 to H should be zero in the first K pairwise XORs.
    Then we handle such an array of segments B that all pairwise XORs that we need can be obtained as pairwise XORs on each segment. In fact these segments are non-intersecting and their union is [0,N). Each segment is composed of these numbers A[i] that have equal bits from h+1 to H. Then we divide each such segment according to the h-th bit and check the condition similar to those for the H-th bit (sum CNT(CNT-1)/2*) for divided segments. If K<=SUM then for the next bit we will be in this case again. Otherwise we have to add all pairwise XORs for all segments to the answer, decrease K by SUM and create an array of pairs of segments C={([L1i,R1i), [L2i,R2i)):1<=i<=Nh} with meaning that our remaining pairwise XORs included in XORs of the form A xor B where A belongs to [L1i,R1i) and B belongs to [L2i,R2i) for every i.

  2. We have an array C of pairs of segments and required pairwise XORs included in pairwise XORs of numbers in segments of C as described above.
    Now the consideration is a bit different. Let’s consider a pair of segments [L1,R1), [L2,R2). Then on [L1,M1) we have zero h-th bit for all A[i], L1 <= i < M1 and on [M1,R1) - unit h-th bit. M2 has the same meaning. Then zero h-th bit has pairwise XORs of segments [L1,M1) and [L2,M2) and also [M1,R1) and [M2,R2). So there are (M2-L2) * (M1-L1)+(R1-M1) * (R2-M2) numbers in total. If the sum S of all these numbers for all pairs of segments is more or equal to K then our K XORs are among them and we replace each pair {[L1,R1), [L2,R2)} by two pairs {[L1,M1), [L2,M2)} and {[M1,R1), [M2,R2)} and pass to (h-1)-th bit. Otherwise we have to add all these pairwise XORs to the resulting array, decrease K by S and replace each pair {[L1,R1), [L2,R2)} by two pairs {[L1,M1), [M2,R2)} and {[M1,R1), [L2,M2)} (where h-th is equal to one). But if in some pair we have an empty segment this pair should be ignored. Hence, B and C have no more than N segments. After we pass 0-th bit we still may have some segments or pairs of segments left. In fact each segment now contains equal numbers. So pairwise XORs would also be equal and we can analyze this case easily.

Finally we sort the result array and print it.

P.S: Such a solution worked for 0.6-0.8 sec. on a maximal test case, so the Time Limit wasn’t really strict.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes