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
achaitanyasai , thank you for looking into this. I did change it, this is the new solution:http://www.codechef.com/viewsolution/4339421
Still WA
@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
@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! 
1 Like
I am unable to understand the problem …for 10001 , 10 1000 , 100 10001 , and 1 are also the substrings …isn’t that ??