codeforces-scrape

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

1601A.md (4455B)


      1 Source: https://codeforces.com/problemset/problem/1601/A
      2 
      3 A. Array Elimination
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given array $a_1, a_2, \ldots, a_n$, consisting of non-negative integers.
     22 
     23 Let's define operation of "elimination" with integer parameter $k$ ($1 \leq k \leq n$) as follows:
     24 
     25 * Choose $k$ distinct array indices $1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \le n$.
     26 * Calculate $x = a_{i_1} ~ \& ~ a_{i_2} ~ \& ~ \ldots ~ \& ~ a_{i_k}$, where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND) (notes section contains formal definition).
     27 * Subtract $x$ from each of $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$; all other elements remain untouched.
     28 
     29 Find all possible values of $k$, such that it's possible to make all elements of array $a$ equal to $0$ using a finite number of elimination operations with parameter $k$. It can be proven that exists at least one possible $k$ for any array $a$.
     30 
     31 Note that you firstly choose $k$ and only after that perform elimination operations with value $k$ you've chosen initially.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). Description of the test cases follows.
     36 
     37 The first line of each test case contains one integer $n$ ($1 \leq n \leq 200\,000$) — the length of array $a$.
     38 
     39 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt 2^{30}$) — array $a$ itself.
     40 
     41 It's guaranteed that the sum of $n$ over all test cases doesn't exceed $200\,000$.
     42 
     43 Output
     44 
     45 For each test case, print all values $k$, such that it's possible to make all elements of $a$ equal to $0$ in a finite number of elimination operations with the given parameter $k$.
     46 
     47 Print them in increasing order.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 5
     55 4
     56 4 4 4 4
     57 4
     58 13 7 25 19
     59 6
     60 3 5 3 1 7 1
     61 1
     62 1
     63 5
     64 0 0 0 0 0
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 1 2 4
     71 1 2
     72 1
     73 1
     74 1 2 3 4 5
     75 ```
     76 
     77 Note
     78 
     79 In the first test case:
     80 
     81 * If $k = 1$, we can make four elimination operations with sets of indices $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$. Since $\&$ of one element is equal to the element itself, then for each operation $x = a_i$, so $a_i - x = a_i - a_i = 0$.
     82 * If $k = 2$, we can make two elimination operations with, for example, sets of indices $\{1, 3\}$ and $\{2, 4\}$: $x = a_1 ~ \& ~ a_3$ $=$ $a_2 ~ \& ~ a_4$ $=$ $4 ~ \& ~ 4 = 4$. For both operations $x = 4$, so after the first operation $a_1 - x = 0$ and $a_3 - x = 0$, and after the second operation — $a_2 - x = 0$ and $a_4 - x = 0$.
     83 * If $k = 3$, it's impossible to make all $a_i$ equal to $0$. After performing the first operation, we'll get three elements equal to $0$ and one equal to $4$. After that, all elimination operations won't change anything, since at least one chosen element will always be equal to $0$.
     84 * If $k = 4$, we can make one operation with set $\{1, 2, 3, 4\}$, because $x = a_1 ~ \& ~ a_2 ~ \& ~ a_3 ~ \& ~ a_4$ $= 4$.
     85 
     86 In the second test case, if $k = 2$ then we can make the following elimination operations:
     87 
     88 * Operation with indices $\{1, 3\}$: $x = a_1 ~ \& ~ a_3$ $=$ $13 ~ \& ~ 25 = 9$. $a_1 - x = 13 - 9 = 4$ and $a_3 - x = 25 - 9 = 16$. Array $a$ will become equal to $[4, 7, 16, 19]$.
     89 * Operation with indices $\{3, 4\}$: $x = a_3 ~ \& ~ a_4$ $=$ $16 ~ \& ~ 19 = 16$. $a_3 - x = 16 - 16 = 0$ and $a_4 - x = 19 - 16 = 3$. Array $a$ will become equal to $[4, 7, 0, 3]$.
     90 * Operation with indices $\{2, 4\}$: $x = a_2 ~ \& ~ a_4$ $=$ $7 ~ \& ~ 3 = 3$. $a_2 - x = 7 - 3 = 4$ and $a_4 - x = 3 - 3 = 0$. Array $a$ will become equal to $[4, 4, 0, 0]$.
     91 * Operation with indices $\{1, 2\}$: $x = a_1 ~ \& ~ a_2$ $=$ $4 ~ \& ~ 4 = 4$. $a_1 - x = 4 - 4 = 0$ and $a_2 - x = 4 - 4 = 0$. Array $a$ will become equal to $[0, 0, 0, 0]$.
     92 
     93 Formal definition of bitwise AND:
     94 
     95 Let's define bitwise AND ($\&$) as follows. Suppose we have two non-negative integers $x$ and $y$, let's look at their binary representations (possibly, with leading zeroes): $x_k \dots x_2 x_1 x_0$ and $y_k \dots y_2 y_1 y_0$. Here, $x_i$ is the $i$-th bit of number $x$, and $y_i$ is the $i$-th bit of number $y$. Let $r = x ~ \& ~ y$ is a result of operation $\&$ on number $x$ and $y$. Then binary representation of $r$ will be $r_k \dots r_2 r_1 r_0$, where:
     96 
     97 $$ r_i = \begin{cases} 1, ~ \text{if} ~ x_i = 1 ~ \text{and} ~ y_i = 1 \\ 0, ~ \text{if} ~ x_i = 0 ~ \text{or} ~ y_i = 0 \end{cases} $$