PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Daanish Mahajan
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh
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';
}
}