MINSUB - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

Easy-Medium

PREREQUISITES:

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:

Editorialist’s Solution
Tester-1’s Solution
Tester-2’s Solution
Setter’s Solution

2 Likes
2 
#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.

3

Consider this input:

1
15
110010010100010
4

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

5

#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

6

Hey @man_telent123 :wave: ,
Your code is failing on test case
1
6
101111
Your answer is
111110
111011
where LCS is 4 (1110).

where as correct answer has LCS 3.
example:
110111
111110
LCS 3 (110).