NCOPIES - Editorial

[akashagarwal00]

I guess my code works in O(N) time

CODE:-
ll t;
cin>>t;
while(t–)
{
ll n, m;
string s;

cin >> n >> m >> s;

vi pre(n), suf(n+1);

pre[0] = (s[0] == '0') ? 0 : 1;
suf[n-1] = (s[n-1] == '0') ? 0 : 1;
suf[n] = 0;

for (int i = 1; i < n; ++i) {
  pre[i] = pre[i-1];
  
  if (s[i] == '1')
    ++pre[i];
}

for (int i = n-2; i >= 0; --i) {
  suf[i] = suf[i+1];
  
  if (s[i] == '1')
    ++suf[i];
}

int ones = suf[0];
int goodIndices = 0;

if (ones == 0) {
  cout << n*m << endl;
  continue;
}

for (int i = 0; i < n; ++i) {
  if (
    (pre[i] == suf[i+1] && m%2 == 1) ||
    (pre[i] > 0 && suf[i+1] == 0 && m%2 == 0) ||
    (pre[i] == 0 && suf[i+1] > 0 && m%2 == 0)
  ) {
    ++goodIndices;
  }
}

cout << goodIndices << endl;

}

[rahulfulwa677]

can you explain this logic ?

if (
    (pre[i] == suf[i+1] && m%2 == 1) ||
    (pre[i] > 0 && suf[i+1] == 0 && m%2 == 0) ||
    (pre[i] == 0 && suf[i+1] > 0 && m%2 == 0)
  ) {
    ++goodIndices;
  }

[akashagarwal00]

In 1st condition its checking if it there are equal number of 1s both side and the M is odd , see if you have equal 1s both side that means its a good indices why odd M so that we can have half of the repeatitions to either side and the odd one will be at mid
example :-
5 5
11011

at index 2 you satisfy given condition if i expand it
11011 11011 11011 11011 11011
|

pointed 0 is a good index

At 2 and 3 condition i am checking if all the 1s are at one side and the M is even
example :-
3 4
011
if i expand :
011 011 011 011
|
pointed 0 is a good index
3rd condition is same as 2nd its just change the side like
2 4
110
expand:
110 110 110 110
|

good index

[hk2255]

Hey, can u plz tell which test case this might be failing?

#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include<numeric>
using ll = long long;

// complete this simulation just to understand coding

int main() 
{
	int t;
	cin >> t;
	while(t)
	{
	    t--;
        int n, m;
	    string s;
        cin >> n >> m >> s;

        int cnt1 = 0, cnt0 = 0;

        for (int i = 0; i < n; i++)
        {
            if(s[i] == '1') cnt1++;
            else cnt0++;
        }

        if(cnt1 * m *1LL % 2 == 1) 
        {
            cout << "0" << endl;
            continue;
        }
        else if(cnt1 == 0) 
        {
            cout << cnt0 * m * 1LL << endl;
            continue;
        }
        
        string odd = s;
        string even = s + s;

        int oddind = 0;
        int evenind = 0;

        int count1 = 0;
        for (int i = 0; i < odd.size(); i++)
        {                   
            if(odd[i] == '1') count1++;
            if(count1 == cnt1 / 2) 
            {
                oddind++;
                i++;
                while (odd[i] == '0')
                {
                    i++;
                    oddind++;
                }         
                break;
            }
        }

        count1 = 0;
        for (int i = 0; i < even.size(); i++)
        {
                        
            if(even[i] == '1') count1++;
            if(count1 == cnt1) 
            {
                evenind++;
                i++;
                while (even[i] == '0')
                {
                    i++;                    
                    evenind++;
                }       
                break;         
            }
        }
        
        if(m % 2 == 1)
        {
            cout << oddind << endl;        
        }
        else
        {            
            cout << evenind << endl;                     
        }        
        
    }

	return 0;
}