algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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