PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: satyam_343
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
You’re given N and K.
Construct a binary string of length N such that exactly K of its odd-length substrings have a mode of 1.
EXPLANATION:
We call an odd-length substring valid if it has a mode of 1.
Trying the extremal strings, we find the following:
- S = 000\ldots 000 has zero valid substrings.
- S = 111\ldots 111 has all possible valid substrings.
The count of valid substrings in the second case is N + (N-2) + (N-4) + \ldots, i.e. the count of odd-length substrings of S.
Let this count be T.
If K \gt T then certainly no solution can exist, so we only need to deal with K \in [0, T].
It turns out that a solution always exists for such K.
(There is one exception: N = 3 and K = 2 has no solution, whereas T = 4 for N = 3. This is, however, the only exception - larger N always affords us enough leeway to attain the result.)
We have constructions corresponding to the extreme values, so naturally it’s useful to try and analyze what happens when moving from one to the other.
The simplest way to move from all zeros to all ones is to have a prefix of zeros and a suffix of ones.
Say we have a prefix of N-x zeros and then x ones.
Since the string is sorted, the mode of any odd-length substring is just its middle character.
There are \min(i, N+1-i) odd-length substrings centered about index i.
So, the number of valid substrings equals
In particular, observe that if x \le \frac{N}{2} then the count is just 1+2+\ldots + x.
We’ll use this fact to construct an answer for all K \in [0, \frac{T}{2}].
(Note that T itself equals the sum of \min(i, N+1-i) across all i in the first place, so taking all indices on one half of the string gives us \frac{T}{2}.)
Now that we’re dealing with K \le \frac{T}{2}, let x be the largest integer such that 1+2+\ldots + x \le K.
Let’s start with a string that has N-x zeros as a prefix and x ones as its suffix.
Let R = K - (1+2+\ldots + x) be the remaining number of valid substrings we need.
If R = 0 we’re done, so we can safely assume R \gt 0.
We also know that R \lt x+1, because otherwise it would’ve been optimal to include another 1 instead.
Now consider what happens when we inject a single 0 somewhere into the suffix of 1’s (and of course, remove a 0 from the prefix.)
If we insert if after y ones, the string looks like
For this string, note that:
- The length-1 substring centered at the middle 0 is no longer valid, though everything else centered about it is valid.
So, we lose one valid substring. - For the leftmost 1, there are now an additional x+1 odd-length substrings centered about it which can potentially be valid.
- However, of these, the ones ending at or after the inserted 0 aren’t actually valid because of the extra 0 they’ll contain.
So, there are exactly y new valid substrings with the new center. - For all other centers, it can be verified that the counts of valid substrings centered about them doesn’t change.
So, the change in the count of valid substrings equals exactly y-1, since we lose 1 but gain y.
We’re able to freely choose 1 \le y \le x, which gets us every possible increase from 0 to x-1.
So, all 0 \le R \le x-1 are now solved for with this construction.
Since we know that R \lt x-1, this means the only case that doesn’t yet have a solution is R = x.
To attain this, we use a similar idea.
Let’s start by getting an increase of x-1, which corresponds to the string 00\ldots 00 11\ldots 11 0.
(This is what we get by choosing y=x in the section above.)
We now require one more valid substring.
Once again, this can be achieved by injecting a 0 into the block of ones.
Specifically, injecting it after two ones to obtain
will work, for the same reason as above: we lose one valid substring but obtain two more.
Unfortunately, there are a couple of edge cases here: if x is very small then this construction doesn’t quite work (or, in the case of x=1, isn’t even valid!)
Luckily though “very small” x here refers to just x \le 3 or so, which caps us at K \le 6.
It’s easy enough to solve such small cases by simply bruteforcing the answer for small N, and then extending the solution to larger N by just padding with zeros.
All together, we now have a way to construct an answer for all K \in [0, \frac{T}{2}].
For the larger values of K, note that if we take a binary string with K valid substrings and flip all its characters (i.e. 0 \leftrightarrow 1 ), then every odd-length substring will swap between being valid and invalid.
So, the flipped string will have exactly (T-K) valid substrings.
This allows us to solve for \frac{T}{2} \lt K \le T by first solving for T-K (which is now \le \frac{T}{2}), and then simply flipping all characters in the answer!
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define ld long double
#define nline "\n"
#define f first
#define s second
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define sz(x) (ll)x.size()
#define vl vector<ll>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;
const ll MAX=500500;
void solve(){
ll n,k; cin>>n>>k;
auto sum_till=[&](ll x){
return x*(x+1)/2;
};
auto add=[&](char c,ll cnt){
if(cnt<=0){
return string("");
}
return string(cnt,c);
};
auto getv=[&](ll x){
if(x==0){
return string("");
}
ll l=0,r=n,till=0;
while(l<=r){
ll mid=(l+r)/2;
if(sum_till(mid)<=x){
till=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
ll rem=x-sum_till(till);
string s="";
if(rem==0){
s+=add('0',till-1);
s+=add('1',till);
}
else if(rem<till){
s+=add('0',till-1);
s+=add('1',rem+1);
s+='0';
s+=add('1',till-rem-1);
}
else{
if(till==1){
s="1001";
}
else if(till==2){
s="10011";
}
else if(till==3){
s="0011100";
}
else{
s+=add('0',till-2);
s+="110";
s+=add('1',till-2);
s+='0';
}
}
return s;
};
ll even=n/2+1;
ll odd=(n+1)/2;
ll total=even*odd;
if((k<0) or (k>total)){
cout<<-1<<nline;
return;
}
if((n==3) and (k==2)){
cout<<-1<<nline;
return;
}
ll rev=0,x=k;
if(2*k>total){
x=total-k;
rev=1;
}
string suf=getv(x);
if(sz(suf)>n){
cout<<-1<<nline;
return;
}
string ans(n-sz(suf),'0');
ans+=suf;
if(rev){
for(auto &it:ans){
if(it=='0'){
it='1';
}
else{
it='0';
}
}
}
std::reverse(ans.begin(), ans.end());
cout<<ans<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
}