algorithms

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

problem.txt (1859B)


      1 F1. XOR Transformations (Easy Version)
      2 time limit per test
      3 4 seconds
      4 memory limit per test
      5 512 megabytes
      6 
      7 This is the easy version of the problem. The difference between the versions is that in this version, the constraints on n and q are smaller. You can make hacks only if you have solved all versions of this problem.
      8 
      9 For an array b consisting of m integers, define a transformation as follows:
     10 
     11     Write down the values bi⊕bj for all 1≤i<j≤m, where ⊕ denotes the bitwise XOR operation..
     12     Take the m smallest among the written values.
     13     Replace the elements of the array with the taken m values. 
     14 
     15 For example, consider the transformation of the array [6,7,8,9,15]. We write down the values 1,1,6,7,8,9,14,14,15,15. After the transformation, the array becomes [1,1,6,7,8] — the 5 smallest elements.
     16 
     17 You are given an array a consisting of n non-negative integers. Let max(a) denote the maximum element of the array a, and min(a) — the minimum. Your task is to answer q queries, each of which gives you one integer x. For each query, find the value of max(a)−min(a) after x transformations on the array. Note that the queries are independent, i.e. before each query, the array a is restored to its original state.
     18 Input
     19 
     20 Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). The description of the test cases follows.
     21 
     22 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.
     23 
     24 The second line of each test case contains n integers a1,a2,…,an (0≤ai<230).
     25 
     26 The next q lines of each test case contain an integer x (0≤x<230).
     27 
     28 It is guaranteed that the sum of n and the sum of q over all test cases do not exceed 2000.
     29 Output
     30 
     31 For each test case, output q integers — the answer to each query.