codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2094E.md (1338B)


      1 Source: https://codeforces.com/problemset/problem/2094/E
      2 
      3 E. Boneca Ambalabu
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Boneca Ambalabu gives you a sequence of $n$ integers $a_1,a_2,\ldots,a_n$.
     22 
     23 Output the maximum value of $(a_k\oplus a_1)+(a_k\oplus a_2)+\ldots+(a_k\oplus a_n)$ among all $1 \leq k \leq n$. Note that $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
     24 
     25 Input
     26 
     27 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) – the number of independent test cases.
     28 
     29 The first line of each test case contains an integer $n$ ($1 \leq n\leq 2\cdot 10^5$) – the length of the array.
     30 
     31 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \lt 2^{30}$).
     32 
     33 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case, output the maximum value on a new line.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 5
     45 
     46 3
     47 
     48 18 18 18
     49 
     50 5
     51 
     52 1 2 4 8 16
     53 
     54 5
     55 
     56 8 13 4 5 15
     57 
     58 6
     59 
     60 625 676 729 784 841 900
     61 
     62 1
     63 
     64 1
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 0
     71 79
     72 37
     73 1555
     74 0
     75 ```
     76 
     77 Note
     78 
     79 In the first test case, the best we can do is $(18\oplus18)+(18\oplus18)+(18\oplus18)=0$.
     80 
     81 In the second test case, we choose $k=5$ to get $(16\oplus1)+(16\oplus2)+(16\oplus4)+(16\oplus8)+(16\oplus16)=79$.