codeforces-scrape

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

1926D.md (2345B)


      1 Source: https://codeforces.com/problemset/problem/1926/D
      2 
      3 D. Vlad and Division
      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 Vladislav has $n$ non-negative integers, and he wants to divide all of them into several groups so that in any group, any pair of numbers does not have matching bit values among bits from $1$-st to $31$-st bit (i.e., considering the $31$ least significant bits of the binary representation).
     22 
     23 For an integer $k$, let $k_2(i)$ denote the $i$-th bit in its binary representation (from right to left, indexing from 1). For example, if $k=43$, since $43=101011_2$, then $43_2(1)=1$, $43_2(2)=1$, $43_2(3)=0$, $43_2(4)=1$, $43_2(5)=0$, $43_2(6)=1$, $43_2(7)=0$, $43_2(8)=0, \dots, 43_2(31)=0$.
     24 
     25 Formally, for any two numbers $x$ and $y$ in the same group, the condition $x_2(i) \neq y_2(i)$ must hold for all $1 \leq i \lt 32$.
     26 
     27 What is the minimum number of groups Vlad needs to achieve his goal? Each number must fall into exactly one group.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     32 
     33 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the total number of integers.
     34 
     35 The second line of each test case contains $n$ given integers $a_1, \ldots, a_n$ ($0 \leq a_j \lt 2^{31}$).
     36 
     37 The sum of $n$ over all test cases in a test does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output a single integer  — the minimum number of groups required to satisfy the condition.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 9
     49 
     50 4
     51 
     52 1 4 3 4
     53 
     54 2
     55 
     56 0 2147483647
     57 
     58 5
     59 
     60 476319172 261956880 2136179468 1671164475 1885526767
     61 
     62 3
     63 
     64 1335890506 811593141 1128223362
     65 
     66 4
     67 
     68 688873446 627404104 1520079543 1458610201
     69 
     70 4
     71 
     72 61545621 2085938026 1269342732 1430258575
     73 
     74 4
     75 
     76 0 0 2147483647 2147483647
     77 
     78 3
     79 
     80 0 0 2147483647
     81 
     82 8
     83 
     84 1858058912 289424735 1858058912 2024818580 1858058912 289424735 122665067 289424735
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 4
     91 1
     92 3
     93 2
     94 2
     95 3
     96 2
     97 2
     98 4
     99 ```
    100 
    101 Note
    102 
    103 In the first test case, any two numbers have the same last $31$ bits, so we need to place each number in its own group.
    104 
    105 In the second test case, $a_1=0000000000000000000000000000000_2$, $a_2=1111111111111111111111111111111_2$ so they can be placed in the same group because $a_1(i) \ne a_2(i)$ for each $i$ between $1$ and $31$, inclusive.