codeforces-scrape

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

2179D.md (2361B)


      1 Source: https://codeforces.com/problemset/problem/2179/D
      2 
      3 D. Blackslex and Penguin Civilization
      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 Penguins are civilized creatures that communicate using permutations. Blackslex, as a penguin researcher, must study their means of communication.
     22 
     23 For a given integer $n$, consider permutations$^{\text{∗}}$ $p$ of the array $[0, 1, \ldots, 2^n - 1]$. Define $$S(p) \;=\; \sum_{i=0}^{2^n-1} \operatorname{popcount}\!\bigl(p_0 \mathbin{\&} p_1 \mathbin{\&} \cdots \mathbin{\&} p_i\bigr),$$ where $\operatorname{popcount}(z)$ is the number of $1$-bits in the binary representation of $z$ (for instance, $\operatorname{popcount}(5) = 2$ because $5 = 101_2$ has two $1$-bits in the binary representation), and $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). .
     24 
     25 A permutation is considered sacred if it maximizes $S(p)$. Find the lexicographically minimal$^{\text{†}}$ sacred permutation.
     26 
     27 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
     28 
     29 $^{\text{†}}$An array $a$ is lexicographically smaller than an array $b$ of the same size if and only if the following holds:
     30 
     31 * in the first position where $a$ and $b$ differ, the array $a$ has a smaller element than the corresponding element in $b$.
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \le t \le 16$) — the number of test cases.
     36 
     37 Each test case contains a single integer $n$ ($1 \le n \le 16$).
     38 
     39 It is guaranteed that the sum of $2^n$ over all test cases does not exceed $2^{16}$.
     40 
     41 Output
     42 
     43 For each test case, output $2^n$ integers $p_0, p_1, \ldots, p_{2^n-1}$ — the required permutation.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 2
     51 
     52 1
     53 
     54 2
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 1 0
     61 
     62 3 1 0 2
     63 ```
     64 
     65 Note
     66 
     67 For the first test case, there are two possible permutations.
     68 
     69 * $p = [0, 1]$, $S(p) = 0$
     70 * $p = [1, 0]$, $S(p) = 1$
     71 
     72 For the second test case, $S([3, 1, 0, 2]) = 3$ is sacred. There are other permutations $p$ that are sacred, such as $p = [3, 2, 0, 1]$, but those are not lexicographically minimal.