Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

And... Yet Another AND Problem

By YouKnowWho · Limits 1s, 512 MB

YouKn0wWho has an integer nn. He wants to find an integer sequence aa of size exactly 2n2n such that 0ai<2n0 \le a_i \lt 2^n for each valid ii and for each integer kk from 00 to 2n12^n - 1, there exists at least one non-empty subsequence of aa such that the bitwise AND of the elements of that subsequence is kk.

Help YouKn0wWho find such a sequence. If there are multiple such sequences, output any. It can be shown that such a sequence always exists under the given constraints.

A sequence bb is a subsequence of a sequence cc if bb can be obtained from cc by deletion of several (possibly, zero or all) elements.


The first and only line of the input will contain single integer n(1n18)n \, (1 \le n \le 18).


Output 2n2n integers a1,a2,a2n(0ai<2n)a_1, a_2, \ldots a_{2n}(0 \le a_i \lt 2^n) such that it satisfies the conditions mentioned in the statement. If there are multiple such sequences, output any.


1 0
3 1 0 2
4 3 5 6 7 1

In the third test case, you can achieve each integer from 00 to 231=72^3-1=7 as bitwise AND of the elements of some non-empty subsequence of aa:

  • a1&a3&a6=4&5&1=0a_1 \mathbin{\&} a_3 \mathbin{\&} a_6 = 4 \mathbin{\&} 5 \mathbin{\&} 1 = 0

  • a6=1a_6=1

  • a2&a4&a5=3&6&7=2a_2 \mathbin{\&} a_4 \mathbin{\&} a_5 = 3 \mathbin{\&} 6 \mathbin{\&} 7 = 2

  • a2=3a_2 = 3

  • a1=4a_1 = 4

  • a3=5a_3=5

  • a4&a5=6&7=6a_4 \mathbin{\&} a_5 = 6 \mathbin{\&} 7 = 6

  • a5=7a_5 = 7

Here, &\& is the bitwise AND operator.



    71% Solution Ratio

    Noshin_1703086Earliest, 1w ago

    Hotash_MeyeFastest, 0.0s

    Noshin_1703086Lightest, 131 kB

    FrdhsnShortest, 356B


    Login to submit


    I will use 0-indexing here. For n=5n=5n=5, consider the following 555 numbers (shown in binary): a0=...

    Toph uses cookies. By continuing you agree to our Cookie Policy.