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

4 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…

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

Change int to long long

1 Like

achaitanyasai , thank you for looking into this. I did change it, this is the new solution:http://www.codechef.com/viewsolution/4339421

Still WA

@dorsatum change flag to long long… link to AC – http://www.codechef.com/viewsolution/4339523

1 Like

@shivam217, thank you!

@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

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: http://www.codechef.com/viewsolution/4368543

nC2 = n*(n-1)/2

@miamiheat- avoid allocating large memory inside the loop … you could have made a static array of max=10^5 outside the loop… here youtry to allocate t*n times inside which is 10^5 * 10^5 … and btw, for this question, you dont have to allocate an array… you could have done input with one variable only! :slight_smile:

1 Like

Thanks man :slight_smile:

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

//