thoughts.txt (1510B)
1 - Array b of m integers 2 - Write down the values bi⊕bj for all 1≤i<j≤m, where ⊕ denotes the bitwise XOR operation.. 3 - so xor between b_i and b_j where both are valid and i < j 4 - take m smallest 5 - replace the elements of the array with the m selections 6 7 --- 8 9 [6,7,8,9,15] 10 11 We write down the values 1,1,6,7,8,9,14,14,15,15 12 13 [6,7,8,9,15] 14 15 6 xor 7, 6 xor 8, 6 xor 9, 6 xor 15, 6 xor 7, ... 16 17 then sort and select the first m elements (not necessarily sort but def 18 lowest 5) 19 20 --- 21 22 given a of size n with non-negative numbers 23 24 for each element of array a, x: 25 - perform x transformations 26 - return max(a) - min(a) 27 - each query is independent so we mustn't manipulate the underlying collct. 28 29 --- 30 31 The first line of each test case contains two integers n and q (5≤n≤2000,1≤q≤2000) — the size of the array and the number of queries. 32 33 The second line of each test case contains n integers a1,a2,…,an (0≤ai<230). 34 35 The next q lines of each test case contain an integer x (0≤x<230). 36 37 It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 2000. 38 39 output: 40 41 For each test case, output q integers — the answer to each query. 42 43 --- 44 45 - approach: 46 - we could just find the largest x and answer all incremental steps 47 - this would just use memoization 48 - there's an alt approach that'd track which states we care about too 49 - math approach 50 - xor has some nice properties, perhaps there's something there