SDSTRING - Editorial

PROBLEM LINK

Contest

Setter : Jeevan Jyot Singh
Tester : Rahul Dugar
Editorialist : Rajarshi Basu

PREREQUISITES

None

DIFFICULTY

Simple

PROBLEM

A binary string is called a self-destructing string if it can reduced to an empty string by performing the following operation some number of times (possibly zero): Choose a valid integer i such that the i-th character of the current string is different from the i+1-th character, and remove these two characters from the string.

You are given a binary string s. Your task is to convert s to a self-destructing string. To do that, you may perform the following operation any number of times (possibly zero): Choose an integer i (1 \le i \le |s|-1) such that the i-th character of s is different from the i+1-th character, and invert one of these characters (inverting a character means changing β€˜0’ to β€˜1’ or β€˜1’ to β€˜0’, e.g. the string β€œ01” can be changed to β€œ00”).

Find the smallest number of operations required to convert s to a self-destructing string or determine that it is impossible.

Constraints

  • 1 \le T \le 1,000
  • 1 \le |s| \le 10^6
  • s contains only characters β€˜0’ and β€˜1’
  • the sum of |s| over all test cases does not exceed 10^6

EXPLANATION

The following are the cases :

  • the string has odd number of characters. Then, it is obviously impossible since every deletion operation doesn’t change the parity of length.
  • If the string has only 0’s or 1’s then we cannot do a change operation, and it is also non reducible, so its impossible.
  • Otherwise it is just the difference between number of 1’s and 0’s, divided by 2.

SOLUTION

Tester’s Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
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;
			}
			assert(l<=x && x<=r);
			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,' ');
}
 
int suss=0;
void solve() {
	string s=readStringLn(1,1000000);
	for(char i:s)
		if(i!='0'&&i!='1')
			assert(0);
//	cin>>s;
//	suss+=sz(s);
//	assert(suss<=1000000);
	if(sz(s)&1) {
		cout<<-1<<endl;
	} else {
		int ones=accumulate(all(s),0LL)-(sz(s)*'0');
		if(ones==sz(s)||ones==0)
			cout<<-1<<endl;
		else
			cout<<max(ones-sz(s)/2,sz(s)/2-ones)<<endl;
	}
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(7);
	int t=readIntLn(1,1000);
//	int t=1;
//	cin>>t;
	fr(i,1,t)
		solve();
//	assert(getchar()==EOF);
#ifdef rd
//	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}

VIDEO EDITORIAL (English):

VIDEO EDITORIAL (Hindi):

why is this condition important??

  • If the string has only 0’s0’s or 1’s1’s then we cannot do a change operation, and it is also non reducible, so its impossible.

authors @rajarshi_basu plz reply to this query

1 Like