CSUB - Editorial

It has to be nc1 + nc2 where n = no of zeros in string, in more detail, right?

Why this gets a WA even though I took care of overflow?
#include
#include

using namespace std;

int main(){
	int T;
	cin>>T;
	for(int t=1;t<=T;t++){
		int N;
		cin>>N;
		
		char str[1];
		long long int ones=0,substrings=0;
		
		for(int i=0;i<N;i++){
			cin>>str[0];
			if(strcmp(str,"1")==1){
				ones++;
			}
		}
		if(ones==1){
			substrings = 1;
		}
		else{
			substrings = ones*(ones-1);
			substrings = substrings/2;
			substrings = substrings + ones;
		}
		cout<<substrings<<endl;
	}
}

Please provide explanation on how you came up with this formula.

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

    #include <bits/stdc++.h> 

#include
#include
using namespace std;

int main()
{
int t,i,c=0,j=0,n;
string s1,s2;
cin>>t;
while(t–){
cin>>n;
for(i=0;i<n;i++){
cin>>s1[i];
}
for(i=0;i<n;i++){
if(s1[i]==‘1’){
j=i;
while(j<n){
if(s1[j]==‘1’)
{c++; }
j++;
}
}
}
cout<<c<<"\n";
c=0;
}
}

Pls help.Why I am getting runtime ?

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Edit:

It’s because you’re trying to place chars at the ith index of s1 for i = 0 … n:

for(i=0;i<n;i++){
            cin>>s1[i];
        }

when s1 is empty.

because of this

#include <bits/stdc++.h> 
#include <string>
using namespace std; 
  
int main() 
{ 
    long int t,i,j=0,n;
    long long int c=0;
    string s1;
    cin>>t;
    while(t--){
        cin>>n;
        for(i=0;i<n;i++){
            cin>>s1[i];
        }
        for(i=0;i<n;i++){
            if(s1[i]=='1'){
                j=i;
                while(j<n){
                    if(s1[j]=='1')
                    {
                        c++; 
                    }
                    j++;
                }   
            }
        }
        cout<<c<<"\n";
        c=0;
    }
} 

It is running but on submission it is giving runtime error.

1 Like

Pls explain.I’m not able to understand

Try reading this:

why is my code getting wrong answer https://www.codechef.com/viewsolution/28566482

how can “long int count” instead of “int count” make wrong answer right?my submission bcame successful when i used long int count.
https://www.codechef.com/viewsolution/29154571

Where is my code is wrong i donot understand.Please Explain.

#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–){
int n;
cin>>n;
string str;
cin>>str;
int count=0;
for(int i=0;i<n;i++){
if(str[i]==‘1’){
count++;
}
}
int ans=0;
if(count==1){
ans=count;
}else if(count==2){
ans=3;
}else{
ans=(count+1)*(count);
ans=ans/2;
}
// cout<<count<<endl;
cout<<ans<<endl;
}
return 0;
}

The constraint for n is 1<=n<=10^5 but we had to take long long for storing the count value of 1’s
but count value of 1’s must be less than or equal to 10^5.
Can someone explain me why???

You don’t have to, but it makes it easier to avoid overflow when computing (num1s * (num1s - 1))/2. You could also do e.g.:

#include <iostream>

using namespace std;

int main()
{
    int T;
    cin >> T;

    for (int t = 0; t < T; t++)
    {
        int n;
        cin >> n;

        string binaryString;
        cin >> binaryString;

        int num1s = 0;
        for (const auto bit : binaryString)
        {
            if (bit == '1')
                num1s++;
        }

        cout << (static_cast<long long int>(num1s) * (num1s - 1)) / 2 << endl;
    }
}

Quite often Competitive Programmers will use long long int or an equivalent instead of int for all variables as it can be less error-prone.

2 Likes

Take c as long long int.

Count of 1 can be as high as 10^5 , and when you multiply it n*(n+1), its goes out of range , thus we need to take long long int for n.

Can some check what is the error in my code, i used something like two pointer to count starting 1 and added all the ending 1’s after that pointer
https://www.codechef.com/viewsolution/38096948

It is a kind of easy question but the thing is it is a bit incomplete in terms of test cases this maybe improved

e.g= for test case 10101 the answer should be [0,0] ,[2,2],[4,4] [4,0] but the solution in editor will give 6.

If number of discontinued zeros are counted and subtracted from the solution we will get 4.

but again in testcase 10001 the answer is 3 but according to what I said above it will subtract 1 from 3 and give 2, which is a wrong answer.

so there should be a specific condition to tackle this problem.

@admin @devuy11

@aditya26m The answer for 10101 will be 6.
for 10101
we will get 3 substring [0,0] ,[2,2],[4,4]. And other 3 are [0,4] ,[0,2],[2,4].
So total 6.