ODDARY - Editorial

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

  1. Any two consecutive strings differ at exactly one position
  2. All N+1 strings are distinct
  3. 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';
    }

}
3 Likes

Honestly one of the worst problems I’ve seen lately. The idea can be guessed easily, why the hell is this an easy-medium? It’s not even that fun type of greedy construction where you spot a property, but just playing around works, at least that’s how I solved it.

Not trying to put shame on the author, but this one doesn’t deserve a place in the remaining rather good problemset at all, in my opinion.

BTW, sure the editorial proof is interesting and something many people will get to learn from, but it still doesn’t change the fact that it’s a bad problem in a type of contest where proof by AC is enough.

18 Likes

So my approach for the problem was,

  1. Observed that two consecutive element of the array cannot be the same.
  2. Simplest array goes like this 121_
  3. Now to fill the 4th place, we cannot take 2, because then the first 4 elements has elements of even frequency.
  4. So we end up with 1213_. Now we can fill the next 3 positions with 121 and array becomes 1213121.
  5. Now for the 8th place, we cannot take 3. Hence we’ll need new element, i.e. 4.
    Now the pattern seems evident and construction of this vector is left.
    My solution
    Solution: 50086660 | CodeChef
26 Likes

I was thinking the same, but what happens after 8th place?? Can u please give the answer for n=16

For 16, the answer will be like this:
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5

2 Likes

My simple divide and conquer recursive solution: Solution: 50104882 | CodeChef

Approach:
If there is a unique element in array then all the subarrays to its left and right which include that element will always be valid, now just recursively think of this, divide the array at the position of that unique element and treat left and right part of the array as independent array.

To achieve the minimal value of maximum value in array you need to divide array as low as possible, to do this divide array at mid always, maintain a counter, increment counter at each iteration, set mid element value to counter. This is kind of like merge-sort divide and conquer minus the merge part and only including divide part.

2 Likes

Consider 1213121 this as a string = y;
now for 8th place, my array becomes y+4
now for 9th position onward the string will y+4+y
Now consider this as a new string z = y+5+y;
now the array will be z+5+z.
For n=16, following this pattern, my answer which is printed will be
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5

2 Likes

Can you please tell me for n=8, why is 1 2 3 2 1 2 3 2 wrong?

1 Like

In the whole string the frequency of each number is even. Thus, it is wrong.

2 Likes

Consider whole array as subarray
Frequency of 1 = 2 (which is even)
frequency of 2 = 4 (which is even)
frequency of 3 = 2(which is even)
Question says there shouldn’t exist a subarray that has all elements occurring in even frequency.

what is the proof that while merging mean’s when comming back to form [L,R] by (l1,r1) and (l2,r2) to smaller part to bigger part then all the elements will not have even frequency ?
could you explain please?

While merging the elements, the mid element itself will be included, since we are considering middle element to be unique hence its frequency is 1 always in the given context of division. First just imagine whole array, put ‘a’ in mid and assume ‘a’ to be unique so ‘a’ frequency in array is 1, now all the subarrays to the left and to the right that INCLUDES ‘a’ (mid element) are valid since ‘a’ frequency is 1 and it cannot be anywhere else.

Now divide the array at the mid point, now you got two more arrays after dividing the array, treat them independently, and now put ‘b’ in middle of each of them which is to be unique to that divided array. Now you may ask what if i take subarray which includes both this ‘b’ and ‘a’ inserted at previous step, then that case will fall under the previous explanation which proves it to be valid subarray.

My solution was inspired by this post Google coding interview question - Codeforces here the guy is checking for validity of array I used the same process to construct the array rather than checking, if you scroll down there you will find more detailed explanation.

2 Likes

Nice Editorial!

1 Like

Yess makes sense. Thank u…

1 Like

my aimple solution is giving wrong answer… rather it is similar to all succesfully submitted code of others
https://www.codechef.com/viewsolution/50115077

For N = 1000, the answer will contain 10.
Since you’ve represented the answer using a string though, what gets stored is char('0' + 10) which is :, so you end up printing that instead of 10.

Store the answer in an array/vector and I think you will get AC.
It’s an unfortunate mistake.

10
1 2 3 4 5 6 7 8 9 10

1
1 2
1 2 1
1 2 3 2
1 2 3 2 1
1 2 3 2 1 2
1 2 3 2 1 2 3
1 2 3 4 3 2 1 2
1 2 3 4 3 2 1 2 3
1 2 3 4 3 2 1 2 3 4
someone please correct me if the above output is wrong for the given n

Since N is small, you can simply bruteforce.
https://www.codechef.com/viewsolution/50102062

How did you know that the max value possible in the output array is 11.

Given N you can find out max value using the formula: Floor(log base 2 ( N )) + 1