 # CSUB - Editorial

Author: Lalit Kundu
Tester: Shang Jingbo and Gerald Agapov
Editorialist: Devendra Agarwal

Cakewalk

### PROBLEM:

Given a string S consisting of only 1’s and 0’s, find the number of substrings which start and end both in 1.

### Quick Explanation

You need to find number of pairs of 1.

### Explanation

Find total number of 1’s in the given string. Let suppose that the total number of 1’s in the string is n , then the answer is (n*(n+1))/2.

Reason

Let’s suppose that the n 1’s in the string occur at x1 , x2, … , xn position in the string then all substring starting from xi and ending at xj are taken, so total possible ways in taking it is (n*(n+1))/2

Pseudo Code

``````solve(string s)
int n = 0
for ( i = 0 ; i< s.size() ; i++)
if s* == '1'
n++
return (n*(n+1))/2
``````

Complexity:

O(N), You just need a single pass of the string.

### AUTHOR’S and TESTER’S SOLUTIONS:

5 Likes

http://www.codechef.com/viewsolution/4290532

what is the difference?

Due to range (it could cause overflow)…I guess…In highest case value will be (10^5(10^5+1))/2 check the highest value of integer in your compiler by using INT_MAX from . can a int variable hold this much of value?? try long long datatype for holding everything…

2 Likes

http://www.codechef.com/viewsolution/4268643

What is wrong with this one? Says wrong answer, doesn’t seem anything is wrong though. (Submitted during the competition)

Hi,
I did this problem, can anyone please tell what is with my solution as it says wrong answer.I think everything is ok with it.
#include
#include

using namespace std;

//vector v;
void solve()
{
int n, c = 0;
string s;
cin>>n;
cin>>s;
for(int i = 0; i < n; ++i)
{
if(s* == ‘1’)
c++;
}
long long int a = ((c*c) + c)/2;
cout<<a<<endl;
}
int main()
{
int t;
cin>>t;
while(t–)
{
solve();
}

``````return 0;
``````

}

this is the main program of my solution, I don’t think it gives wrong answer also I am using the unsigned long long data type to evaluate the answer, what’s the problem with this solution to the problem?

``````int main(){

int T;
cin >> T;

for(int i = 0 ; i < T ; ++i){

int N;
cin >> N;

cin.ignore();

string bitString;
getline(cin,bitString);

int countOnes = 0;

for(int j = 0 ; j < (int)bitString.length() ; ++j){
if(bitString[j] == '1')
++countOnes;
}

ULL product = countOnes*(countOnes + 1);
cout << product/2 << endl;
}

return 0;
}``````

Hi, my code runs for all the test cases. But the final result is WA, this is my code, any ideas?

http://www.codechef.com/viewsolution/4339360

@ankitsablok89 The problem is due to overflow . In your code countOnes in of int type , so when you mutiply countOnes*(countOnes+1) , the ans would be of int type . If countOnes = 10^5 , then overflow would occur . To solve the problem you can cast it to long long type . Here is your corrected

``````
.

: http://www.codechef.com/viewsolution/4341226``````

Why is my code results “Time Limit Exceeded”

#include<stdio.h>
main()
{
long long int result;
long int i,t,n,count;
char s;
scanf("%ld",&t);
while(t–)
{
count=0;
scanf("%ld",&n);
s = (char
)malloc(sizeof(char)(n+1));
fflush(stdin);
gets(s);
for(i=0;i<n;i++)
if(s
==‘1’)
count++;
result = (count*(count-1))/2 + count;
printf("%lld
",result);
}
return 0;
}

Why is my code results “Time Limit Exceeded”
Code is here: http://www.codechef.com/viewplaintext/4298438

Why is my code results “SIGSEGV” Code is here: http://www.codechef.com/viewsolution/4368543

I am unable to understand the problem …for 10001 , 10 1000 , 100 10001 , and 1 are also the substrings …isn’t that ??

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

Can someone provide me with a test case for which my code is wrong. It is running perfect still i am getting WA.
https://www.codechef.com/viewsolution/14664852

can someone tell me what’s wrong in this code,thanks in advance.
https://www.codechef.com/viewsolution/15359934

I am not sure what is wrong with this code : https://www.codechef.com/viewsolution/16553453

Its executing completely fine with my IDE (DevC++) but CodeChef is showing WA. Can anyone pls help ?

Someone please clarify : We are essentially choosing two 1’s from a string of n 1’s, so basically, we need to do nC2, right? Then by this the solution should be (n*(n-1))/2! Where am I going wrong?

Hi. I’m not able to understand how and where I went wrong even though it displays the correct answer for the practice cases:

#include
using namespace std;

int main()

{
string s;

``````unsigned long long int t,n,count,i;
char c;
cin>>t;
for(int o=0;o<t;o++)
{
cin>>n;
count=0;
for(i=0;i<n;i++)
{
cin>>c;
if(c=='1')
count++;
}
if(count%2)
cout<<((count+1)/2)*count;
else
cout<<((count/2)*(count+1));

}
``````

}

Could someone please explain how we got the formula?

Could someone please explain how we got the formula?