 # MINSUB - Editorial

Setter: Kanhaiya Mohan
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

Easy-Medium

None

# PROBLEM:

You are given a binary string A of length N. Rearrange the binary string to form binary strings S and T such that the length of the longest common substring between S and T is minimum.

Print both strings S and T.

Note that both S and T must be anagrams of A — see the examples below for more clarity.

# EXPLANATION:

Let cnt_0 denotes the number of 0s in the string A, and let cnt_1 denotes the number of 1s. Without loss of generality, let us assume that cnt_0 \geq cnt_1.

Consider any string S. The $1$s in the string will be partitioning the string into cnt_1 + 1 blocks having non-negative number of 0s. By pigeonhole principle, at least one of the blocks will have \lceil \frac{cnt_0}{cnt_1 + 1} \rceil 0s. This means that the longest common substring will atleast have these many $0$s. This argument suggests us that we should have our S in such a way that $0$s are grouped as evenly as possible.

Examples

So, if A = 00000011, we should have S = 00100100. If we have A = 000000011, we should have S = 001001000. For now, let’s try to put extra 0s towards the end blocks. The reason will soon become clear.

After constructing S, we want to construct T so as to minimize the length of longest common substring. For this, we can greedily group all the 0s together, and all the 1s together. But should 0s come before 1s or vice-versa? Note that because of our construction of S, we have greater number of 0s towards end. A corner case arises when only the last partition contains larger number of 0s as compared to other partitions, as this partition is preceded by a 1 but is not followed by a 1. This suggests that we should first have 0s, and then 1s in T.

Examples

If A = 000000011, then we have S = 001001000.
Now, if T = 110000000, we have a common substring of length 4, as the last 1 of S is also getting matched. However, if we put T = 000000011, we will have a common substring of length 3 only, which is minimum as we discussed above.

# TIME COMPLEXITY:

O(N) or O(N \cdot \log{N}) for each test case, depending on the implementation.

# SOLUTION:

2 Likes
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#define pb push_back
#define mp make_pair
#define ff first
#define rz resize
#define ss second
#define endl "\n"

#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

using namespace std;

#ifndef ONLINE_JUDGE
#define debug(x) cerr<< #x <<" "; _print(x); cerr<<endl;
#else
#define debug(x)
#endif

template <class T> void _print(T t) { cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T> void _print(stack <T> v);
template <class T> void _print(stack <T> v) {cerr << "[ "; while(!v.empty()) {_print(v.top());v.pop(); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); 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 << "]";}
template <class T> void _print(vector < vector <T> > v){cerr<<"["<<endl; {for(vector<T> vec1:v){for(T x:vec1){cerr<<x<<" ";}cerr<<endl;}}cerr<<"]";}
ll gcd(ll a,ll b){if(a==0)return b; return gcd(b%a,a);}

ll power(ll x, unsigned int y){
ll res = 1;
x = x % MOD;
if (x == 0) return 0;
while (y > 0){
if (y & 1)res = (res*x) % MOD;
y = y>>1;
x = (x*x) % MOD;
}
return res;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("/Users/loukiknaik/Desktop/Contest/run/Error.txt", "w",stderr);
freopen("/Users/loukiknaik/Desktop/Contest/run/input.txt","r",stdin);
freopen("/Users/loukiknaik/Desktop/Contest/run/output1.txt","w",stdout);
#endif
fastio
ll t;
cin>>t;
while (t--)
{
ll n,i,j,k,l,m;
cin>>n;
string str;
cin>>str;
debug(str.length())
ll c1=0,c0=0;
for(auto x:str){
if(x=='1')
c1++;
else
c0++;
}
string s1="",s2="";
if(c1==c0){
k=c0;
while(k--)
s1+='0';
k=c1;
while(k--)
s1+='1';
k=c0;
while(k--)
s2+="10";
}
else if(c1>c0){
k=c0;
while(k--)
s1+='0';
k=c1;
while(k--)
s1+='1';
k=c1;
l=ceil(float(c1)/float(c0+1));
// debug(l)
j=1;
ll one=0,zero=0;
if(c1%(c0+1)==1){
for(i=1;i<=c1;i++){
s2+='1';
one++;
if(j%l==0 && (i!=c1 || c1==c0))
{
s2+='0';
zero++;
j=1;
}
j++;
}
if(zero!=c0)
s2+='0';
}
else{
ll one=0,zero=0;
for(i=1;i<=c1;i++){
s2+='1';
one++;
if(i%l==0 && (i!=c1 || c1==c0))
{
s2+='0';
zero++;
}
}
if(zero!=c0)
s2+='0';
}
debug(s1)
debug(s2)
}
else{
k=c1;
while(k--)
s1+='1';
k=c0;
while(k--)
s1+='0';
k=c0;
l=ceil(float(c0)/float(c1+1));
ll one=0;
if(c0%(c1+1)==1){
j=1;
for(i=1;i<=c0;i++){
s2+='0';
if(j%l==0 && i!=c0)
{
s2+='1';
one++;
j=1;
}
j++;
}
if(one!=c1)
s2+='1';
}
else{
for(i=1;i<=c0;i++){
s2+='0';
if(i%l==0 && i!=c0)
{
s2+='1';
one++;
}
}
if(one!=c1)
s2+='1';
}
debug(s1)
debug(s2)
}
cout<<s1<<"\n"<<s2<<"\n";
}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}



Can anyone suggest a testcase for which this code gives wrong output
https://www.codechef.com/viewsolution/61484062.

Consider this input:

1
15
110010010100010


It is possible to build S and T in a few lines of code and O(N):
https://www.codechef.com/viewsolution/61363604

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define vll vector

#define pi (3.141592653589)

#define mod 1000000007

#define float double

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

#define all(c) c.begin(), c.end()

#define min3(a, b, c) min(c, min(a, b))

#define min4(a, b, c, d) min(d, min(c, min(a, b)))

#define max3(a, b, c) max(c, max(a, b))

#define max4(a, b, c, d) max(d, max(c, max(a, b)))

#define rfo(i, j, n) for (int i = n - 1; i >= j; i–)

#define fo(i, j, n) for (int i = j; i < n; i++)

#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

void solve()

{

int n;

cin >> n;

string s, even, odd;

cin >> s;

string temp = s, str = "";

for (auto x : s)

{

if ((x - '0') % 2 == 0)

{

even.pb(x);

}

else

odd.pb(x);

}

if (even.size() > odd.size())

{

sort(all(temp));

int x = even.size() / (odd.size() + 1);

if (even.size() % (odd.size() + 1) >=odd.size())

{

x++;

}

string s1 = "";

fo(i, 0, x)

{

s1 += '0';

}

fo(i, 0, odd.size())

{

str += s1;

str += '1';

}

int z = x * odd.size();

int y = even.size() - z;

int i = 0;

while (i++ < y)

{

str += '0';

}

cout << temp << endl;

cout << str << endl;

}

else

{

sort(all(temp), greater<int>());

int x = odd.size() / (even.size() + 1);

if (odd.size() % (even.size() + 1) >= even.size())

{

x++;

}

string s1 = "";

fo(i, 0, x)

{

s1 += '1';

}

fo(i, 0, even.size())

{

str += s1;

str += '0';

}

int z = x * even.size();

int y = odd.size() - z;

int i = 0;

while (i++ < y)

{

str += '1';

}

cout << temp << endl;

cout << str << endl;

}


}

int32_t main()

{

int t = 1;

cin >> t;

while (t--)

{

solve();

}

return 0;


}

can anyone find out why i am got wrong ans

Hey @man_telent123 ,
Your code is failing on test case
1
6
101111