BINMIS-Editorial

PROBLEM LINK:

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

Setter: Divyansh Gupta
Tester: Nishank Suresh, Satyam
Editorialist: Devendra Singh

DIFFICULTY:

Easy

PREREQUISITES:

Count of a unique element in any range of an array using concept similar to prefix sum .

PROBLEM:

You have a binary string S of length N.

You must perform the following operation on the binary string S exactly once:

  • Choose two integers L and R (1 \le L \le R \le N) and invert the substring S_{L \dots R} (i.e change 1 to 0 and change 0 to 1).

Determine whether you can make the number of zeroes in S equal to number of ones in S by performing the above operation exactly once. If there exists a way, also output the bounds of the chosen substring.

QUICK EXPLANATION:

Whenever the length of the string is even it is possible to make the count of zeroes and count of ones equal by inverting some prefix of the string.

EXPLANATION:

If N is odd the count of zeroes and ones in the string can never be made equal as addition of two same numbers is even. Therefore when N is odd the answer is always NO. Now, we will prove that when N is even it is always possible to invert some prefix of the string to make the count of ones and the count of zeroes in the string equal.
Let P_i represent the prefix of the string S ending at index i \:i.e. substring formed by the first i characters of the string SS[1..........i]. Let the difference between the count of ones and the count of zeroes in string S be a.
Suppose we invert the complete string S the difference now becomes -a. Also, Inverting P_1 changes a by 2 and Inverting P_2 changes the difference obtained by inverting P_1 again by 2. Overall, Inverting P_{i+1} changes the difference obtained on inverting P_i by 2. This means by inverting prefixes of different length we can make difference equal to all values from -a to a where adjacent values differ by 2. Let a>0 then some possible differences are -a, -a+2..........a-2, a.
Also as the length of the string S is even therefore either both the count of zeroes and count of ones in string S are even or they both are odd. This means that initial difference a is an even number. This means that the possible difference take the value of all even numbers between -a to a which includes 0.
Lets Ones_i represent the numbers of 1 in the prefix of length i. We just need to find an index i such that inverting P_i makes the count of zeroes and the count of ones equal to N/2. This boils down to finding an index i such that Ones_n-N/2=2\cdot Ones_i - i.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
#include<bits/stdc++.h>
#include<string>

using namespace std;

#define ll long long int
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define deb(x) cout<< #x << '=' << x <<endl
#define MOD 1000000007

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin>>t;

    for(int tc = 1; tc <= t; tc++){
        ll n;
        cin>>n;

        string s;
        cin>>s;

        if(n % 2 == 1){
            cout<<"nO\n";
        }else{
            ll ones = 0 , zeroes = 0;
            for(int i = 0; i < n; i++){
                ones += (s[i] == '1');
                zeroes += (s[i] == '0');
            }

            ll req = (ones - zeroes)/2 , cur = 0 , l = 1 , r = 1;
            for(int i = 0; i < n; i++){
                cur += (s[i] == '1');
                cur -= (s[i] == '0');

                if(cur == req){
                    r = i + 1;
                    break;
                }
            }
            cout<<"YeS\n";
            cout<<l<<" "<<r<<"\n";
        }
    }   
    return 0;
}
Tester-1's Solution (Python)
for _ in range(int(input())):
	n = int(input())
	s = input()
	if n%2 == 1:
		print('NO')
	else:
		print('YES')
		dif = s.count('1') - s.count('0')
		curdif = 0
		for i in range(n):
			if s[i] == '0':
				curdif -= 1
			else:
				curdif += 1
			if 2*curdif == dif:
				print(1, i+1)
				break

Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif 
 
 
/*
------------------------Input Checker----------------------------------
*/
 
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,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
int MAX=100000;
int check_bin(string s){
    for(auto it:s){
        if((it!='0')&&(it!='1')){
            return 0;
        }
    }
    return 1;
}
int sum_cases=0;
void solve(){
    int n=readIntLn(1,MAX); 
    sum_cases+=n;
    string s=readStringLn(n,n);
    assert(check_bin(s));
    vector<int> freq(5,0);
    for(auto it:s){
        freq[it-'0']++;
    }       
    int req=freq[1]-freq[0];  
    int now=0;     
    map<int,int> prvs; prvs[0]=1;  
    s=" "+s;     
    if(abs(req)&1){  
        cout<<"NO\n";
        return;
    }
    req/=2;
    for(int i=1;i<=n;i++){
        if(s[i]=='1'){
            now--;
        }
        else{
            now++;
        }
        if(prvs[now+req]!=0){
            cout<<"YES\n";
            cout<<prvs[now+req]<<" "<<i<<"\n";
            return;
        }
        prvs[now]=i+1; 
    }
    cout<<"NO\n";
    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         
    int test_cases=readIntLn(1,10000); 
    while(test_cases--){
        solve();
    }
    assert(getchar()==-1);
    assert(sum_cases<=(2*MAX)); 
    return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(),_obj.end()
#define F first
#define S second
#define pll pair<ll, ll> 
#define vll vector<ll>
const int N=1e5+11,mod=1e9+7;
ll max(ll a,ll b) {return ((a>b)?a:b);}
ll min(ll a,ll b) {return ((a>b)?b:a);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n;
cin>>n;
string s;
cin>>s;
if(n&1)
{
    cout<<"NO"<<'\n';
    return ;
}
int p[n+1]={0};
for(int i=1;i<=n;i++)
p[i]=p[i-1]+(s[i-1]=='1');
for(int i=1;i<=n;i++)
{
    if(p[n]-(n/2)==2*p[i]-i)
    {
        cout<<"YES"<<'\n'<<1<<' '<<i<<'\n';
        break;
    }
}
return ;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int test=1;
    cin>>test;
    while(test--) sol();
}

1 Like

I don’t know where I am wrong.
unable to think any testcases for which the code fails.

My approach:

  1. count zeros and ones , if they are equal we are done.
  2. Otherwise, if zero are more than ones, in that case i am converting zero and ones according to the code.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
   
    while(t--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        int flag = 0;
        if(n%2!=0)
        {
            cout<<"NO\n";
            continue;
        }
        else
        {
            
            int z = 0,o = 0;
            for(int i=0;i<n;i++)
            {
                if(s[i]=='0')
                {
                    z++;
                }
                else{
                    o++;
                }
            }
            
            if(z==o)
            {
                cout<<"YES\n";
                cout<<1<<" "<<n<<"\n";
                flag = 1;
            }
            else if(z>o)
            {
                
                int req = (z + o)/2;
                int x = z - req + o;
                
                int a = x;
                int b = o;
                int l = a+b;
                int i=0,j=0;
                int c1=0,c2 = 0;
                while(j<n)
                {
                    if(s[j]=='0')
                    {
                        c1++;
                    }
                    else {
                        c2++;
                    }
                    if(j-i+1<l)
                    {
                        j++;
                    }
                    else if(j-i+1==l)
                    {
                        if(c1 == a and c2 == b)
                        {
                            cout<<"YES\n";
                            cout<<i+1<<" "<<j+1<<"\n";
                            flag = 1;
                            break;
                        }
                        if(s[i]=='0')
                    {
                        c1--;
                    }
                    else {
                        c2--;
                    }
                        i++;
                        j++;
                    }
                }
            }
            else
            {
                int req = (z + o)/2;
                int x = o - req + z;
                
                int a = z;
                int b = x;
                int l = a+b;
                int i=0,j=0;
                int c1=0,c2 = 0;
                while(j<n)
                {
                    if(s[j]=='0')
                    {
                        c1++;
                    }
                    else {
                        c2++;
                    }
                    if(j-i+1<l)
                    {
                        j++;
                    }
                    else if(j-i+1==l)
                    {
                        if(c1 == a and c2 == b)
                        {
                           cout<<"YES\n";
                            cout<<i+1<<" "<<j+1<<"\n";
                            flag = 1;
                            break;
                        }
                        if(s[i]=='0')
                    {
                        c1--;
                    }
                    else {
                        c2--;
                    }
                        i++;
                        j++;
                    }
                }
            }
            if(flag == 0)
                cout<<"NO\n";
        }
    }
    return 0;
}

I had the same. I don’t know which test cases I am not able to tackle.
Can someone please help?

void solve()
{
     ll n;
     cin>>n;
     string s;
     cin>>s;
     vi a(2,0);
     rep(n)
     {
        a[s[i]-'0']++;
     }
     debug(a[0])
     debug(a[1])
     if(n%2)
     {
        cout<<"NO"<<nline;
        return;
     }
     if(a[0]==a[1])
     {
        // cout<<"YES"<<nline;
        // cout<<2232;
        rep(n)
        {
            if(s[i]!=s[i+1])
            {
                cout<<"YES"<<nline;
                cout<<i+1<<" "<<i+2<<nline;
                return;
            }
        }

     }
     if(a[0]>a[1])
     {
        ll x=a[0]-n/2;
        ll cnt=0;
        ll last=1;
        for(ll i=0;i<n;i++)
        {
            if(s[i]=='0')
                cnt++;
            else
                {
                    cnt=0;
                    last=i+2;
                }
            if(cnt==x)
            {
                cout<<"YES"<<nline;
                cout<<last<<" "<<i+1<<nline;
                return;

            }
        }
     }
     else
     {
        ll x=a[1]-n/2;
        debug(x)
        ll cnt=0;
        ll last=1;
        for(ll i=0;i<n;i++)
        {
            if(s[i]=='1')
                cnt++;
            else
                {
                    cnt=0;
                    last=i+2;
                }
            if(cnt==x)
            {
                cout<<"YES"<<nline;
                cout<<last<<" "<<i+1<<nline;
                return;
            }
        }
     }
       
  cout<<"NO"<<nline;

}

Me to same approach but got WA , anyone please let me know the case where this approach fails

inverting prefixes of different length we can make difference equal to all values from -a to a where adjacent values differ by 2.

i think difference can be more than a also
as, if we flip 1st index then diff can be a±2
so can you explain why diff would be between -a and a

I don’t know why my code is failing in some of the subtasks . Anyone please help me out finding the mistake i’m doing .

Approach :
(a) if ones == zeroes , simply take the whole substring to print .
(b) if ones > zeroes , then i need to decrease the count of ones by (ones -zeroes)/2 so
that the no of ones gets decreased and no of zeroes get increased and becomes
equal in count .
So, I simply trying to find (ones -zeroes)/2 no of consecutive ones and inverting it
to zero.
(c) similarly , if zeroes > ones we are decreasing count of zeroes by (zeroes - ones)/2
and finding (zeroes -ones)/2 consecutive zeroes.

                     Here is my code below - 

                     #include<bits/stdc++.h>
                     using namespace std;
                     typedef long long ll;

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

void solve() {

ll n;
cin >> n;

string s;
cin >> s;

if(n%2 == 1)
{
    cout << "NO\n";
    return;
}

ll ones = 0, zeroes = 0;

for(int i=0;i<n;i++)
{
    if(s[i] == '0') zeroes++;
    else ones++;
}

if(ones == zeroes)
{
    cout << "YES\n";
    cout << "1 " << n << endl;
    return;
}


if(ones > zeroes)
{
    int change = (ones - zeroes)/2;
    
    int one_cons = 0 , start = -1;

    for(int i=0;i<n;i++)
    {
       if(s[i] == '1')
       {
           one_cons++;
           if(start == -1)
             start = i;
       }
       else
       {
           if(one_cons >= change)
           {
               cout << "YES\n";
               cout << start + 1 << " " << start + change  << endl;
               return;
           }
           
           one_cons = 0;
           start = -1;
       }
    }
    
           if(one_cons >= change)
           {
               cout << "YES\n";
               cout << start + 1 << " " << start + change  << endl;
               return;
           }
    
}
else if(zeroes > ones)
{
    int change = (zeroes - ones)/2;
    
    int zero_cons = 0 , start = -1;

    for(int i=0;i<n;i++)
    {
       if(s[i] == '0')
       {
           zero_cons++;
           if(start == -1)
             start = i;
       }
       else
       {
           if(zero_cons >= change)
           {
               cout << "YES\n";
               cout << start + 1 << " " << start + change  << endl;
               return;
           }
           
           zero_cons = 0;
           start = -1;
       }
    }
    
           if(zero_cons >= change)
           {
               cout << "YES\n";
               cout << start + 1 << " " << start + change  << endl;
               return;
           }
}

}

int main() {

// #ifndef ONLINE_JUDGE
// freopen(“input.txt”, “r”, stdin);
// freopen(“output.txt”, “w”, stdout);
// #endif

int t = 1;
cin >> t;

for(int i=1;i<=t;i++)
{
    // cout << "Case #";
    // cout << i;
    // cout << ":" << " ";
    solve();
}

}

4 Likes

@dash2199 @iceknight1093 @satyam_343 @devendra7700
Hey guys! I really have no Idea why did my code fails on some of the test cases during the contest.
Could you please provide me a test case where the following code will fail.

#include<bits/stdc++.h>

constexpr char endline = '\n';

int main(){
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int T;
    std::cin >> T;
    while(T--){
        int n;
        std::cin >> n;
        std::string s;
        std::cin >> s;
        if(n & 1){
            std::cout << "NO" << endline;
            continue;
        }
        int one = 0, zero = 0;
        for(int i = 0; i < n; ++i){
            one += s[i] == '1';
            zero += s[i] == '0';
        }
        if(one == zero){
            std::cout << "YES" << endline;
            std::cout << 1 << ' ' << n << endline;
            continue;
        }
        int len = std::max(zero, one) - n / 2;
        char target = one > zero ? '1' : '0';
        int i = 0, x = 0, y = 0;
        bool ok = false;
        while(i < n){
            if(s[i] != target){
                ++i;
                continue;
            }
            int cnt = 0;
            while(i < n && cnt < len && s[i] == target){
                ++i;
                ++cnt;
            }
            if(cnt == len){
                ok = true;
                x = i - cnt;
                y = i - 1;
                break;
            }
        }
        if(ok){
            std::cout << "YES" << endline;
            std::cout << x + 1 << ' ' << y + 1 << endline;
        }else{
            std::cout << "NO" << endline;
        }
    }

    return 0;
}

  1. If N is odd the the answer will be NO.
  2. No. of 1’s == No. of 0’s, answer is YES. (Invert the whole string i.e [1…N]).
  3. No. of 1’s > No. of 0’s, we need to invert the extra ones which is equal to (No. of 1’s - N / 2). We can just find out these much of consecutive one (Which I observed will always exist. I might be wrong) and invert the segment.
  1. No. of 0’s > No. of 1’s (Same approach as for 3)

EDIT:

We can just find out these much of consecutive one (Which I observed will always exist. I might be wrong).

I tried this for smaller string and I concluded that we will always have that kind of substring of required length. Which was completely wrong!

Counter Testcase:

2
18
101110111011010111
16
0001000100010001

Thank you everyone for helping me out.

4 Likes

pleases help me find the test case where my code is failing

import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import java.util.;
import java.io.
;
import java.math.*;

/public cf/class C {

public static void process() throws IOException {
  
//code here
int a,b,c,c1=0,c0=0,l=1,r,count,as=0,ol;
String s;
ol=sc.nextInt();
s=sc.next();
r=s.length();
for(a=0;a<s.length();a++)
{
	if(s.charAt(a)=='1')
	c1++;
	else
	c0++;
}
if(s.length()%2==1)
System.out.println("NO");
else
{b=s.length()/2;
	if(c1>c0)
	{
       count=c1-b;
	   for(a=0;a<s.length();a++)
	   {
          if(s.charAt(a)=='1')
		  as++;
		  else
		  as=0;
		  if(as==count)
		  {
			  r=a+1;
			  break;
		  }
	
	   }
	   l=r-count+1;
	}
	if(c0>c1)
	{
		   count=c0-b;
		   for(a=0;a<s.length();a++)
		   {
			  if(s.charAt(a)=='0')
			  as++;
			  else
			  as=0;
			  if(as==count)
			  {
				  r=a+1;
				  break;
				
			  }
			  
		   }
		   l=r-count+1;
		}
		System.out.println("YES");
		System.out.println(l+" "+r);
	
}

}



//=============================================================================
//--------------------------The End---------------------------------
//=============================================================================
private static long INF = 2000000000000000000L, M = 1000000007, MM = 998244353;
private static int N = 0;

private static void google(int tt) {
	System.out.print("Case #" + (tt) + ": ");
}

static FastScanner sc;
static FastWriter out;

public static void main(String[] args) throws IOException {
	boolean oj = true;
	if (oj) {
		sc = new FastScanner();
		out = new FastWriter(System.out);
	} else {
		sc = new FastScanner("input.txt");
		out = new FastWriter("output.txt");
	}
	long s = System.currentTimeMillis();
	int t = 1;
	t = sc.nextInt();
	int TTT = 1;
	while (t-- > 0) {
		//			google(TTT++);
		process();
	}
	out.flush();
	//		tr(System.currentTimeMillis()-s+"ms");
}

private static boolean oj = System.getProperty("ONLINE_JUDGE") != null;

private static void tr(Object... o) {
	if (!oj)
		System.err.println(Arrays.deepToString(o));
}

static class Pair implements Comparable<Pair> {
	int x, y;

	Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}

	@Override
	public int compareTo(Pair o) {
		return Integer.compare(this.x, o.x);
	}

	/*
	 	@Override
	    public boolean equals(Object o) {
	        if (this == o) return true;
	        if (!(o instanceof Pair)) return false;
	        Pair key = (Pair) o;
	        return x == key.x && y == key.y;
	    }
	 
	    @Override
	    public int hashCode() {
	        int result = x;
	        result = 31 * result + y;
	        return result;
	    }
	*/
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////

static int ceil(int x, int y) {
	return (x % y == 0 ? x / y : (x / y + 1));
}

static long ceil(long x, long y) {
	return (x % y == 0 ? x / y : (x / y + 1));
}

static long sqrt(long z) {
	long sqz = (long) Math.sqrt(z);
	while (sqz * 1L * sqz < z) {
		sqz++;
	}
	while (sqz * 1L * sqz > z) {
		sqz--;
	}
	return sqz;
}

static int log2(int N) {
	int result = (int) (Math.log(N) / Math.log(2));
	return result;
}

public static long gcd(long a, long b) {
	if (a > b)
		a = (a + b) - (b = a);
	if (a == 0L)
		return b;
	return gcd(b % a, a);
}

public static long lcm(long a, long b) {
	return (a * b) / gcd(a, b);
}

public static int lower_bound(int[] arr, int x) {
	int low = 0, high = arr.length - 1, mid = -1;
	int ans = -1;
	while (low <= high) {
		mid = (low + high) / 2;

		if (arr[mid] > x) {
			high = mid - 1;
		} else {
			ans = mid;
			low = mid + 1;
		}
	}

	return ans;
}

public static int upper_bound(int[] arr, int x) {
	int low = 0, high = arr.length - 1, mid = -1;
	int ans = arr.length;
	while (low < high) {
		mid = (low + high) / 2;

		if (arr[mid] >= x) {
			ans = mid;
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	return ans;
}

static void ruffleSort(int[] a) {
	Random get = new Random();
	for (int i = 0; i < a.length; i++) {
		int r = get.nextInt(a.length);
		int temp = a[i];
		a[i] = a[r];
		a[r] = temp;
	}
	Arrays.sort(a);
}

static void ruffleSort(long[] a) {
	Random get = new Random();
	for (int i = 0; i < a.length; i++) {
		int r = get.nextInt(a.length);
		long temp = a[i];
		a[i] = a[r];
		a[r] = temp;
	}
	Arrays.sort(a);
}

static void reverseArray(int[] a) {
	int n = a.length;
	int arr[] = new int[n];
	for (int i = 0; i < n; i++)
		arr[i] = a[n - i - 1];
	for (int i = 0; i < n; i++)
		a[i] = arr[i];
}

static void reverseArray(long[] a) {
	int n = a.length;
	long arr[] = new long[n];
	for (int i = 0; i < n; i++)
		arr[i] = a[n - i - 1];
	for (int i = 0; i < n; i++)
		a[i] = arr[i];
}

//custom multiset (replace with HashMap if needed)
public static void push(TreeMap<Integer, Integer> map, int k, int v) {
	//map[k] += v;
	if (!map.containsKey(k))
		map.put(k, v);
	else
		map.put(k, map.get(k) + v);
}

public static void pull(TreeMap<Integer, Integer> map, int k, int v) {
	//assumes map[k] >= v
	//map[k] -= v
	int lol = map.get(k);
	if (lol == v)
		map.remove(k);
	else
		map.put(k, lol - v);
}

// compress Big value to Time Limit
public static int[] compress(int[] arr) {
	ArrayList<Integer> ls = new ArrayList<Integer>();
	for (int x : arr)
		ls.add(x);
	Collections.sort(ls);
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	int boof = 1; //min value
	for (int x : ls)
		if (!map.containsKey(x))
			map.put(x, boof++);
	int[] brr = new int[arr.length];
	for (int i = 0; i < arr.length; i++)
		brr[i] = map.get(arr[i]);
	return brr;
}

// Fast Writer 

public static class FastWriter {
	private static final int BUF_SIZE = 1 << 13;
	private final byte[] buf = new byte[BUF_SIZE];
	private final OutputStream out;
	private int ptr = 0;

	private FastWriter() {
		out = null;
	}

	public FastWriter(OutputStream os) {
		this.out = os;
	}

	public FastWriter(String path) {
		try {
			this.out = new FileOutputStream(path);
		} catch (FileNotFoundException e) {
			throw new RuntimeException("FastWriter");
		}
	}

	public FastWriter write(byte b) {
		buf[ptr++] = b;
		if (ptr == BUF_SIZE)
			innerflush();
		return this;
	}

	public FastWriter write(char c) {
		return write((byte) c);
	}

	public FastWriter write(char[] s) {
		for (char c : s) {
			buf[ptr++] = (byte) c;
			if (ptr == BUF_SIZE)
				innerflush();
		}
		return this;
	}

	public FastWriter write(String s) {
		s.chars().forEach(c -> {
			buf[ptr++] = (byte) c;
			if (ptr == BUF_SIZE)
				innerflush();
		});
		return this;
	}

	private static int countDigits(int l) {
		if (l >= 1000000000)
			return 10;
		if (l >= 100000000)
			return 9;
		if (l >= 10000000)
			return 8;
		if (l >= 1000000)
			return 7;
		if (l >= 100000)
			return 6;
		if (l >= 10000)
			return 5;
		if (l >= 1000)
			return 4;
		if (l >= 100)
			return 3;
		if (l >= 10)
			return 2;
		return 1;
	}

	public FastWriter write(int x) {
		if (x == Integer.MIN_VALUE) {
			return write((long) x);
		}
		if (ptr + 12 >= BUF_SIZE)
			innerflush();
		if (x < 0) {
			write((byte) '-');
			x = -x;
		}
		int d = countDigits(x);
		for (int i = ptr + d - 1; i >= ptr; i--) {
			buf[i] = (byte) ('0' + x % 10);
			x /= 10;
		}
		ptr += d;
		return this;
	}

	private static int countDigits(long l) {
		if (l >= 1000000000000000000L)
			return 19;
		if (l >= 100000000000000000L)
			return 18;
		if (l >= 10000000000000000L)
			return 17;
		if (l >= 1000000000000000L)
			return 16;
		if (l >= 100000000000000L)
			return 15;
		if (l >= 10000000000000L)
			return 14;
		if (l >= 1000000000000L)
			return 13;
		if (l >= 100000000000L)
			return 12;
		if (l >= 10000000000L)
			return 11;
		if (l >= 1000000000L)
			return 10;
		if (l >= 100000000L)
			return 9;
		if (l >= 10000000L)
			return 8;
		if (l >= 1000000L)
			return 7;
		if (l >= 100000L)
			return 6;
		if (l >= 10000L)
			return 5;
		if (l >= 1000L)
			return 4;
		if (l >= 100L)
			return 3;
		if (l >= 10L)
			return 2;
		return 1;
	}

	public FastWriter write(long x) {
		if (x == Long.MIN_VALUE) {
			return write("" + x);
		}
		if (ptr + 21 >= BUF_SIZE)
			innerflush();
		if (x < 0) {
			write((byte) '-');
			x = -x;
		}
		int d = countDigits(x);
		for (int i = ptr + d - 1; i >= ptr; i--) {
			buf[i] = (byte) ('0' + x % 10);
			x /= 10;
		}
		ptr += d;
		return this;
	}

	public FastWriter write(double x, int precision) {
		if (x < 0) {
			write('-');
			x = -x;
		}
		x += Math.pow(10, -precision) / 2;
		//		if(x < 0){ x = 0; }
		write((long) x).write(".");
		x -= (long) x;
		for (int i = 0; i < precision; i++) {
			x *= 10;
			write((char) ('0' + (int) x));
			x -= (int) x;
		}
		return this;
	}

	public FastWriter writeln(char c) {
		return write(c).writeln();
	}

	public FastWriter writeln(int x) {
		return write(x).writeln();
	}

	public FastWriter writeln(long x) {
		return write(x).writeln();
	}

	public FastWriter writeln(double x, int precision) {
		return write(x, precision).writeln();
	}

	public FastWriter write(int... xs) {
		boolean first = true;
		for (int x : xs) {
			if (!first)
				write(' ');
			first = false;
			write(x);
		}
		return this;
	}

	public FastWriter write(long... xs) {
		boolean first = true;
		for (long x : xs) {
			if (!first)
				write(' ');
			first = false;
			write(x);
		}
		return this;
	}

	public FastWriter writeln() {
		return write((byte) '\n');
	}

	public FastWriter writeln(int... xs) {
		return write(xs).writeln();
	}

	public FastWriter writeln(long... xs) {
		return write(xs).writeln();
	}

	public FastWriter writeln(char[] line) {
		return write(line).writeln();
	}

	public FastWriter writeln(char[]... map) {
		for (char[] line : map)
			write(line).writeln();
		return this;
	}

	public FastWriter writeln(String s) {
		return write(s).writeln();
	}

	private void innerflush() {
		try {
			out.write(buf, 0, ptr);
			ptr = 0;
		} catch (IOException e) {
			throw new RuntimeException("innerflush");
		}
	}

	public void flush() {
		innerflush();
		try {
			out.flush();
		} catch (IOException e) {
			throw new RuntimeException("flush");
		}
	}

	public FastWriter print(byte b) {
		return write(b);
	}

	public FastWriter print(char c) {
		return write(c);
	}

	public FastWriter print(char[] s) {
		return write(s);
	}

	public FastWriter print(String s) {
		return write(s);
	}

	public FastWriter print(int x) {
		return write(x);
	}

	public FastWriter print(long x) {
		return write(x);
	}

	public FastWriter print(double x, int precision) {
		return write(x, precision);
	}

	public FastWriter println(char c) {
		return writeln(c);
	}

	public FastWriter println(int x) {
		return writeln(x);
	}

	public FastWriter println(long x) {
		return writeln(x);
	}

	public FastWriter println(double x, int precision) {
		return writeln(x, precision);
	}

	public FastWriter print(int... xs) {
		return write(xs);
	}

	public FastWriter print(long... xs) {
		return write(xs);
	}

	public FastWriter println(int... xs) {
		return writeln(xs);
	}

	public FastWriter println(long... xs) {
		return writeln(xs);
	}

	public FastWriter println(char[] line) {
		return writeln(line);
	}

	public FastWriter println(char[]... map) {
		return writeln(map);
	}

	public FastWriter println(String s) {
		return writeln(s);
	}

	public FastWriter println() {
		return writeln();
	}
}

// Fast Inputs
static class FastScanner {
	//I don't understand how this works lmao
	private int BS = 1 << 16;
	private char NC = (char) 0;
	private byte[] buf = new byte[BS];
	private int bId = 0, size = 0;
	private char c = NC;
	private double cnt = 1;
	private BufferedInputStream in;

	public FastScanner() {
		in = new BufferedInputStream(System.in, BS);
	}

	public FastScanner(String s) {
		try {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		} catch (Exception e) {
			in = new BufferedInputStream(System.in, BS);
		}
	}

	private char getChar() {
		while (bId == size) {
			try {
				size = in.read(buf);
			} catch (Exception e) {
				return NC;
			}
			if (size == -1)
				return NC;
			bId = 0;
		}
		return (char) buf[bId++];
	}

	public int nextInt() {
		return (int) nextLong();
	}

	public int[] readArray(int N) {
		int[] res = new int[N];
		for (int i = 0; i < N; i++) {
			res[i] = (int) nextLong();
		}
		return res;
	}

	public long[] readArrayLong(int N) {
		long[] res = new long[N];
		for (int i = 0; i < N; i++) {
			res[i] = nextLong();
		}
		return res;
	}

	public int[][] readArrayMatrix(int N, int M, int Index) {
		if (Index == 0) {
			int[][] res = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++)
					res[i][j] = (int) nextLong();
			}
			return res;
		}
		int[][] res = new int[N][M];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++)
				res[i][j] = (int) nextLong();
		}
		return res;

	}

	public long[][] readArrayMatrixLong(int N, int M, int Index) {
		if (Index == 0) {
			long[][] res = new long[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++)
					res[i][j] = nextLong();
			}
			return res;
		}
		long[][] res = new long[N][M];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++)
				res[i][j] = nextLong();
		}
		return res;

	}

	public long nextLong() {
		cnt = 1;
		boolean neg = false;
		if (c == NC)
			c = getChar();
		for (; (c < '0' || c > '9'); c = getChar()) {
			if (c == '-')
				neg = true;
		}
		long res = 0;
		for (; c >= '0' && c <= '9'; c = getChar()) {
			res = (res << 3) + (res << 1) + c - '0';
			cnt *= 10;
		}
		return neg ? -res : res;
	}

	public double nextDouble() {
		double cur = nextLong();
		return c != '.' ? cur : cur + nextLong() / cnt;
	}

	public double[] readArrayDouble(int N) {
		double[] res = new double[N];
		for (int i = 0; i < N; i++) {
			res[i] = nextDouble();
		}
		return res;
	}

	public String next() {
		StringBuilder res = new StringBuilder();
		while (c <= 32)
			c = getChar();
		while (c > 32) {
			res.append(c);
			c = getChar();
		}
		return res.toString();
	}

	public String nextLine() {
		StringBuilder res = new StringBuilder();
		while (c <= 32)
			c = getChar();
		while (c != '\n') {
			res.append(c);
			c = getChar();
		}
		return res.toString();
	}

	public boolean hasNext() {
		if (c > 32)
			return true;
		while (true) {
			c = getChar();
			if (c == NC)
				return false;
			else if (c > 32)
				return true;
		}
	}
}

}

a help would be really appriciated

Did u got that test case in which your answer is coming wrong as i am getting same issue

Try running your code for this test case, and you will find your mistake:
18
101110111011010111

Correct ans: YES, 1 8

2 Likes

1
16
0001000100010001

The logic should fail for this case. There will be others too. Its expected output should be -

Yes
1 8
1 Like

1
16
0001000100010001

The logic should fail for this case. There will be others too. Its expected output should be -

Yes
1 8
2 Likes

I have used the same approach in Java. Upon submitting your solution, I found that both our solution are working only for task 5, 6 and 8.

Initially, I used the same approach but, later on, found some test cases where it fails. These are basically the ones in which we could not find the required number of consecutive zeroes/ones.
some examples:
n=32
00000000000001000000000000010000
00000000000001000000000000100000
00000000000001000000000001000000
00000000000001000000000010000000
00000000000001000000000100000000
in all of the above examples, I need 14 consecutive zeroes to invert, but none of them contains it.

Solved it using two pointer approach.
Link to solution

I used the following approach !
If n is odd, print NO
if count(1) == count(0), print whole substring
otherwise, let the difference between count(1) and count(0) be d
We need to invert exactly d/2 1s to 0 (D will always be even, because since N is even, the both will be either even, or both will be odd.

We can prove, that we can always find a substring of all 1s of d/2, considering that we have more ones than zeros.

So I am finding the biggest substring of all 1s (or 0s, if we have more zeros than 1), and just fix that substring bound to fit for d/2.

The code is Solution: 62856521 | CodeChef

I do not know on which testcase it will fail. If someone can provide an insight, that will be very helpful.

1 Like

https://www.codechef.com/viewsolution/62892832

Why is this not being accepted?

Did you find any case? I am also looking for this.

Got WA,
my approach

  1. If the binary string length is odd return NO
  2. If ones are zeros are even returned (YES, 1, len(strr))
  3. if ones > zeros:
    diff= ones- len(strr) //2
    substrr = ‘1’*diff
    if strr.find(substrr):
    print(YES)
    print the index
  4. if zeros > ones:
    diff= zeros- len(strr) //2
    substrr = ‘0’*diff
    if strr.find(substrr):
    print(YES)
    print the index

i am having more or less similar code like yours if you get to know where the approach fails please let me know as well.