BIS - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: nakshatraexe
Tester: wasd2401
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You have a binary string S of even length.
You can choose two indices i, j such that both are odd, then swap S_i with S_j and S_{i+1} with S_{j+1}.

Find the maximum possible length of a non-decreasing substring you can obtain after using some operations.

EXPLANATION:

Since N is even, and we can only choose odd i and j, we essentially have with us \frac{N}{2} small strings of length 2 (namely S_1S_2, S_3S_4, \ldots), which can be swapped around as we like.
This means there are four ‘types’ of small strings with us: 00, 01, 10, 11.
Let c_{00} denote the number of strings of this type; similarly for the other three types.

Observe that a sorted substring will look like several zeros followed by several ones.
In particular, since we can freely rearrange the length-2 strings,

  • We can always ensure every occurrence of 00 gets added to this sorted substring, by placing them all together.
    The same holds for every occurrence of 11, which can be placed immediately after all the 00's.
  • If there’s at least one occurrence of 01, it can be used to ‘bridge’ the zeros and the ones, increasing the length by 2.
    Only one occurrence of it can be used in a sorted substring.
  • A 10 can be placed either just before all the 00's, or just after all the 11's - nowhere else can it fit into a sorted substring.

So, we start out with a length of 2\cdot (c_{00} + c_{11}).
If c_{01} \gt 0, add 2 to the answer.
Then, add 1 to the answer for each occurrence of c_{10}, but at most twice.

This can be written compactly as

2c_{00} + 2c_{11} + \min(2, 2c_{01}) + \min(2, c_{10})

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

int main(){
    IOS
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string s;
        cin>>s;
        int a=0,b=0,c=0,d=0;
        for(int i=0;i<n;i+=2){
            if(s[i]=='0'&&s[i+1]=='0'){
                a++;
            }
            if(s[i]=='0'&&s[i+1]=='1'){
                b++;
            }
            if(s[i]=='1'&&s[i+1]=='0'){
                c++;
            }
            if(s[i]=='1'&&s[i+1]=='1'){
                d++;
            }
        }
        cout<<2*a+2*min(1,b)+min(2,c)+2*d<<'\n';
    }
    return 0;
}
Tester's code (C++) 
/*

*       *  *  ***       *       *****
 *     *   *  *  *     * *        *
  *   *    *  ***     *****       *
   * *     *  * *    *     *   *  *
    *      *  *  *  *       *   **

                                 *
                                * *
                               *****
                              *     *
        *****                *       *
      _*     *_
     | * * * * |                ***
     |_*  _  *_|               *   *
       *     *                 *  
        *****                  *  **
       *     *                  ***
  {===*       *===}
      *  IS   *                 ***
      *  IT   *                *   *
      * RATED?*                *  
      *       *                *  **
      *       *                 ***
       *     *
        *****                  *   *
                               *   *
                               *   *
                               *   *
                                ***   

*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()

const ll N = 2e5 + 4;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;

ll modinverse(ll a) {
	ll m = mod, y = 0, x = 1;
	while (a > 1) {
		ll q = a / m;
		ll t = m;
		m = a % m;
		a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0) x += mod;
	return x;
}
ll gcd(ll a, ll b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
	return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
	ll product = 1;
	a %= md;
	while (b) {
		if (b & 1) product = (product * a) % md;
		a = (a * a) % md;
		b /= 2;
	}
	return product % md;
}
void panipuri() {
	ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
	string s;
	bool ch = true;
	cin >> n>>s;
	fors(i,0,n,2){
		if(s[i]=='1' && s[i+1]=='0') c++;
		if(s[i]=='0' && s[i+1]=='1') q++;
	}
	cout<<n-2*c-2*q+min(p*2,c)+min(p,q)*2;
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	int laddu = 1;
	cin >> laddu;
	forl(i, 1, laddu + 1) {
		// cout << "Case #" << i << ": ";
		panipuri();
		cout << '\n';
	}
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    ct = [0]*4
    for i in range(0, n-1, 2):
        ct[int(s[i:i+2], 2)] += 1
    ans = 2*(ct[0] + ct[3])
    if ct[1] > 0: ans += 2
    ans += min(2, ct[2])
    print(ans)
1 Like