# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

* Author:* Daanish Mahajan

*Shubham Anand Jain*

**Tester:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Knowledge of what a gray code is (or good constructive ability), Prefix sum arrays

# PROBLEM:

Construct an array of size N such that no subarray has every element occurring with an even frequency. Among all such arrays of size N, the one you construct should minimize the maximum element.

# QUICK EXPLANATION:

The minimum possible maximum element is the smallest k such that 2^k > N. To construct the array on \{1, 2, \dots, k\} build a gray code on k bits and reconstruct the answer from the first N+1 elements of this code.

# EXPLANATION:

The condition on no subarray having every element occur an even number of times is the only information we have, so let’s start with that. Such subarrays will be called **‘bad subarrays’**.

One thing to keep in mind is that whenever subarrays are involved, it is extremely useful to think about prefixes - every subarray is obtained by deleting one prefix from another, after all.

Consider some subarray [L, R] of A, and an element x. What is the parity of the number of occurrences of x in this subarray?

This is where thinking about prefixes helps us:

Suppose we knew par_i(x) - the parity of the number of occurrences in [1, i], for each i. Note that par_i can be thought of as a binary string (of length M, where M is the maximum element in the array), since each value is either 0 or 1.

Then, the value we are looking for is par_R(x) \oplus par_{L-1}(x), where \oplus denotes xor.

In particular, if x occurs an even number of times,

par_R(x) \oplus par_{L-1}(x) = 0 \implies par_R(x) = par_{L-1}(x)

Now, if [L, R] is a bad subarray, that would mean par_R(x) = par_{L-1}(x) for every 1\leq x\leq M - in other words, par_R = par_{L-1} (as strings).

Conversely, if par_R = par_{L-1} for some L\leq R, reversing the argument above tells us that [L, R] has to be a bad subarray.

So, an array A contains no bad subarray if and only if every par_i is a distinct binary string of length M.

### Analyzing par_i

Let’s look at a couple of properties of par_i.

- (Assuming 1-indexing of A) par_0 is all zeroes.
- par_i and par_{i+1} differ at exactly one position.

## Why?

This should be obvious - they differ at exactly position A_{i+1}.

- If we know par_i for every i, we can construct the array A.

## How?

This follows from the first point - we know par_i and par_{i+1}, which means we know A_{i+1}.

Apply this to every 0\leq i < N and we have reconstructed the original array.

So, if we are able to construct a sequence of N+1 binary strings of length M such that

- Any two consecutive strings differ at exactly one position
- All N+1 strings are distinct
- The first string in the sequence is entirely zeroes.

we can use this sequence to construct the array A, as mentioned above. Note that we want to minimize M.

### The construction

There are 2^M binary strings on M bits. We want N+1 distinct binary strings, so the minimum possible value of M at all is the smallest one such that 2^M >= N+1.

It turns out that this M is sufficient as well - all 2^M strings can be arranged in a sequence such that any two consecutive differ at exactly one position, and we simply take the first N+1 of these for our purpose.

Here is one way to construct this sequence:

Let S = \{0, 1\}.

M-1 times, do the following process:

- Let S_0 be the sequence constructed by inserting a 0 at the start of every element of S
- Let S_1 be the sequence constructed by inserting a 1 at the start of every element of the reverse of S
- Set S to be the concatenation of S_0 and S_1.

As an example, here are the first two steps of this process:

S = \{0, 1\}

**Step 1:**

S_0 = \{00, 01\}, S_1 = \{11, 10\}

S = \{00, 01, 11, 10\}

*Step 2:*

S_0 = \{000, 001, 011, 010\}, S_1 = \{110, 111, 101, 100\}

S = \{000, 001, 011, 010, 110, 111, 101, 100\}

\vdots

Note that what is being constructed here is a Gray code on M bits, and there are simpler ways to construct this sequence as well.

For example, it can be shown that the n-th element of this sequence will be n \oplus \lfloor \frac{n}{2}\rfloor (the linked Wikipedia page goes into more detail).

Also see the cp-algo page for more information.

# TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase, depending on how the gray code is constructed.

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000, maxt = 500;
const string newln = "\n", space = " ";
int main()
{
int t; cin >> t;
while(t--){
int n; cin >> n;
int it = 1, pl = 0; vector<int> v;
while(v.size() < n){
v.push_back(it);
for(int i = 0; i < pl; i++)v.push_back(v[i]);
it++; pl = 2 * pl + 1;
}
for(int i = 0; i < n; i++){
cout << v[i] << (i == n - 1 ? newln : space);
}
}
}
```

## Tester's Solution

```
//By TheOneYouWant
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int gray (int n){
return n ^ (n >> 1);
}
int main(){
fastio;
int tests;
cin >> tests;
map<int,int> pow2;
int c = 1;
for(int i = 0; i < 21; i++){
pow2[c] = i+1;
c *= 2;
}
while(tests--){
int n;
cin >> n;
int c = 2, num = 1;
while(c-1<n){
c *= 2;
num++;
}
// 1 to num will be used
// just create gray codes and use
// ignore 0th gray code
int last = 0;
for(int i = 1; i <= n; i++){
int curr = gray(i);
int check = abs(curr - last);
cout << pow2[check] << " ";
last = curr;
}
cout << endl;
}
return 0;
}
```

## Editorialist's Solution

```
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,mmx,avx,avx2")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, pw = 0; cin >> n;
while ((1<<pw) <= n) ++pw;
vector<string> v;
v.push_back(string(pw, '0'));
v.push_back(string(pw, '0'));
v.back()[0] = '1';
for (int i = 1; i < pw; ++i) {
auto w = v; reverse(begin(w), end(w));
for (auto &s : w)
s[i] = '1';
v.insert(end(v), begin(w), end(w));
}
reverse(begin(v), end(v));
for (int i = 0; i < pw; ++i)
if (v[0][i] == '1')
cout << i+1 << ' ';
for (int i = 1; i < n; ++i) {
for (int j = 0; j < pw; ++j) {
if (v[i][j] != v[i-1][j]) cout << j+1 << ' ';
}
}
cout << '\n';
}
}
```