PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: satyam_343
Editorialist: iceknight1093
DIFFICULTY:
2767
PREREQUISITES:
Observation
PROBLEM:
You’re given a binary string S of length N.
In one move, you can pick an index 1 \lt i \lt N, and set S_i = S_{i-1} \oplus S_{i+1}.
Find the maximum possible number of ones you can reach; and the lexicographically smallest string that attains this maximum.
EXPLANATION:
Let’s get a couple of trivial cases out of the way:
- If S contains only zeros, no useful move can be made, so the answer is just S itself.
- If S contains only ones, then it’s already maximum, so again the answer is S itself.
Now, in order for any changes to be made, we’d like our operation to actually be useful, i.e, it should be able to change a 0 to a 1 or vice versa.
In particular, this means:
- If S_i = 0, then S_{i-1} = S_{i+1} makes this index ‘pointless’ to operate on.
- If S_i = 1, then S_{i-1} \neq S_{i+1} makes this index ‘pointless’ again.
If you work out a couple of examples on paper, you’ll notice that there’s a certain class of strings for which every index is pointless, namely:
\texttt{011011011\ldots }, \texttt{110110110\ldots }, \text{ and } \texttt{101101101\ldots }
For these strings, performing an operation on any index will just give you back the same value, so they actually can’t be changed at all.
So, for such strings, the answer is once again S.
With these cases out of the way, we know that S contains at least one 1 and at least one 0, and at least one position where change is possible.
Notice that the operation doesn’t allow us to change the endpoints of S; so they’ll always remain the same.
The best we can hope for is to make all the middle characters of S into 1.
In fact, that’s (almost) always possible!
In particular, the following strings are optimal:
- If S_1 = S_N = 0, we can achieve \texttt{0111\ldots 1110}
- If S_1 = 0 and S_N = 1, we can achieve \texttt{0111\ldots 1111}
- If S_1 = 1 and S_N = 0, we can achieve \texttt{1111\ldots 1110}
- If S_1 = S_N = 1, we can achieve \texttt{1011\ldots 1111}
Note that in this case, it’s not possible to make all the middle characters 1 if they weren’t already that way.
The proof of this is constructive.
Proof
The main idea here is that it’s always possible to reach the state S_1\texttt{000\ldots 000}S_N, i.e, making all the middle characters 0.
That can be done as follows:
- We’ll look at blocks of ones in S.
- If there’s a block of size k\geq 3, it can be split into two smaller blocks of size k-2 and 1, by performing the operation \texttt{111} \to\texttt{101} on the last 3 ones.
Repeatedly perform this operation while it’s possible. - Now, we have only blocks of size 1 and 2.
If there’s a block of size 1 in the middle of the string, it’ll have zeros on both sides; so apply the operation and turn it into a 0.
Again, repeat this while it’s possible. - Now, we have only blocks of size 2, along with possibly blocks of size 1 at the endpoints.
- If a block of size 2 occurs as \texttt{\ldots 01100\ldots} or \texttt{\ldots 00110\ldots}, then again it can be deleted entirely: for example \texttt{01100} \to \texttt{01110} \to \texttt{01010}, then delete the ones.
- The only possible way we have ones remaining in the middle now is if the string looks like \texttt{110110110\ldots} or similar, which we already classified as ‘bad’ strings and took care of.
Further, the way we performed operations, it can be seen that we never reach a ‘bad’ string.
This way, it’s possible to delete all ones from the middle of the string.
Now, if at least one endpoint contains a 1, we can delete all the ones from the middle, then fill them from the endpoint — that is,
\texttt{1000\ldots 000} \to \texttt{1100\ldots 000} \to\texttt{1110\ldots 000} \to\ldots\to \texttt{1111\ldots 10}
If both endpoints are 0, then perform the deletion process above but stop just before the last step.
Now, the string has a single 1, and will look like \texttt{000\ldots 00100\ldots 000}.
From here, again the 1 can be propagated both leftwards and rightwards, to fill everything except the endpoints.
TIME COMPLEXITY
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <math.h>
#include <ctime>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#define int long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
bool isSubstring011(string str) {
string pattern = "011";
string repetition = "";
while (repetition.length() < str.length()+10) {
repetition += pattern;
}
return repetition.find(str) != string::npos;
}
int sumN = 0;
void solve()
{
int n = readInt(1,100000,'\n');
sumN += n;
string s = readStringLn(n,n);
int oneCount = 0;
for(int i = 0; i < n; i++){
assert(s[i] == '0' || s[i] == '1');
oneCount += (s[i] == '1');
}
bool onePresent = (oneCount > 0);
bool oneAtEnd = (s[0] == '1' || s[n-1] == '1');
bool substring011 = isSubstring011(s);
string ansString = "";
if(oneCount == n || oneCount == 0){
ansString = s;
}
else if(onePresent){
if(oneAtEnd){
if(substring011){
ansString = s;
}
else if(s[0] == '1' && s[n-1] == '1'){
ansString += "10";
for(int i = 0; i < n-2; i++){
ansString += "1";
}
}
else if(s[0] == '1'){
for(int i = 0; i < n-1; i++){
ansString += "1";
}
ansString += "0";
}
else{
ansString += "0";
for(int i = 0; i < n-1; i++){
ansString += "1";
}
}
}
else{
if(substring011){
ansString += s;
}
else{
ansString += "0";
for(int i = 0; i < n-2; i++){
ansString += "1";
}
ansString += "0";
}
}
}
cout << ansString;
assert(ansString.length() == n);
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int T=readInt(1,100000,'\n');
while(T--){
solve();
cout<<'\n';
}
assert(getchar()==-1);
assert(sumN <= 1000000);
cerr << sumN << '\n';
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester's code (C++)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=1000100;
ll check(string s,ll n){
for(ll i=1;i<=n-2;i++){
if(s[i-1]==s[i+1]){
if(s[i]!='0'){
debug(i);
return 0;
}
}
else{
if(s[i]=='0'){
debug(i);
return 0;
}
}
}
return 1;
}
void solve(){
ll n; cin>>n;
string s; cin>>s;
string t(n,'0');
if(t==s){
cout<<s<<nline;
return;
}
for(auto &i:t){
i='1';
}
if(t==s){
cout<<s<<nline;
return;
}
if(check(s,n)){
cout<<s<<nline;
return;
}
if(s[0]=='0'){
for(ll i=1;i<=n-2;i++){
s[i]='1';
}
}
if(s[0]=='1' and n>=3){
for(ll i=1;i<=n-2;i++){
s[i]='1';
}
s[1]='0';
}
if(s.back()=='0'){
for(ll i=1;i<=n-2;i++){
s[i]='1';
}
}
cout<<s<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Editorialist's code (Python)
bad = '011'*100006
for _ in range(int(input())):
n = int(input())
s = input()
if s == bad[:n] or s == bad[1:n+1] or s == bad[2:n+2]:
print(s)
continue
if s.count('0') == 0 or s.count('0') == n:
print(s)
continue
if s[0] == '0': print('0' + '1'*(n-2) + s[-1])
else:
if s[-1] == '0': print('1' + '1'*(n-2) + s[-1])
else: print('10' + '1'*(n-2))