CSUB - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Cakewalk

PREREQUISITES:

Adhoc

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[i] == '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:

Author’s solution
Tester’s solution

8 Likes

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

https://codechef_shared.s3.amazonaws.com/download/Solutions/2014/July/Setter/CSUB.cpp (solution of problem setter)

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…

4 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[i] == ‘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


[1].


  [1]: http://www.codechef.com/viewsolution/4341226
1 Like

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[i]==‘1’)
count++;
result = (count
(count-1))/2 + count;
printf("%lld\n",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: CodeChef: Practical coding for everyone

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

somebody please help, whats wrong with this

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 : CodeChef: Practical coding for everyone

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?