BINCON - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

For a binary string S, define f(S) = \{i+j \mid 1 \le i, j \le N, S_i \ne S_j\}.
Given N, find any binary string S of length N that maximizes the size of f(S).

EXPLANATION:

Let’s first figure out the maximum possible value that f(S) can take.

Because 1 \le i, j \le N, we certainly have 2 \le i+j \le 2N.
However, f(S) can never contain either 2 or 2N, because:

  • i+j = 2 is possible only when i=j=1, but in that case S_i \ne S_j cannot hold.
  • Similarly, i+j=2N is possible only with i=j=N but again S_i\ne S_j cannot hold.

So, we’re limited to the range [3, 2N-1].

Let’s see what happens if we try to create all of these values.

To obtain a sum of 3, the only choice is 1+2, so we need S_1 \ne S_2.
Without loss of generality, let S_1 = 1 and S_2 = 0.
Then,

  • To obtain a sum of 4, the options are 2+2 and 1+3.
    2+2 is not viable, so we must use 1+3.
    This forces S_1 \ne S_3 so that S_3 = 0.
  • To obtain 5, the options are 1+4 and 2+3.
    2+3 is not possible because S_2=S_3=0 already.
    So we must use 1+4, forcing S_4 = 0.
  • Similarly to obtain 6, 2+4 and 3+3 are not viable (because the characters are equal already), so we must use 1+5 forcing S_5 = 0.
  • In general, for each 4 \le K \le N+1, if we already have all sums in the range [3, K-1], it can be verified that the only possible option for the sum is 1 + (K-1), which forces S_1 \ne S_K.

So, to end up with all sums from 3 to N+1, we’ll end up with the string

1000\ldots 000

i.e. 1 followed by N-1 zeros.
However, this fixes the entire string - meaning we can’t get any sums larger than N+1 at all!

Clearly, this is not ideal, since we’ve only obtained around half the possible values.

Further, note that this also proves it’s impossible for us to achieve all sums in [3, 2N-1], so at least one of them must be missing.

To do a bit better, note that just like 1000\ldots 000 gives us all the sums in [3, N+1], its reverse 000\ldots 0001 gives us all sums in the range [N+1, 2N-1].

Combining these two strings into

100\ldots 001

i.e. a string with all zeros except the first and last characters, will give us all sums in [3, 2N-1] except for N+1.

Since only one value is missing - which we saw earlier is the best we can do - this string is optimal.

Note that you will have to handle N = 2 separately because 11/00 are not valid answers - but either 10 or 10 will do.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
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(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;

        if (n == 2) cout << "01" << '\n';
        else cout << "1" << string(n-2, '0') << "1" << '\n';
    }
}
2 Likes