×

# 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[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:

This question is marked "community wiki".

46273842
accept rate: 0%

nC2 = n*(n-1)/2

(23 Jul '14, 09:07)

(02 Oct '17, 15:07)

 0 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? answered 14 Jul '14, 21:24 -104●2●3●8 accept rate: 0%
 0 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... answered 14 Jul '14, 22:25 4★sayaksan 26●1●4 accept rate: 0%
 0 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) answered 15 Jul '14, 14:21 46●1●1●3 accept rate: 0%

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 <string>

using namespace std;

//vector<int> 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;


}

-4124
accept rate: 0%

 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; }  answered 16 Jul '14, 14:16 1●2●2●3 accept rate: 0%
 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 answered 17 Jul '14, 20:36 2★dorsatum 1●1 accept rate: 0% 1 Change int to long long (17 Jul '14, 20:49) achaitanyasai , thank you for looking into this. I did change it, this is the new solution:http://www.codechef.com/viewsolution/4339421 Still WA (17 Jul '14, 21:05) dorsatum2★ 1 @dorsatum change flag to long long.. link to AC -- http://www.codechef.com/viewsolution/4339523 (17 Jul '14, 21:42) @shivam217, thank you! (18 Jul '14, 13:06) dorsatum2★
 0 @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 code. answered 18 Jul '14, 13:46 4★the65bit 1.1k●10●13●28 accept rate: 13%

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; }

13113
accept rate: 0%

 0 Why is my code results "Time Limit Exceeded" Code is here: http://www.codechef.com/viewplaintext/4298438 answered 21 Jul '14, 16:25 13●1●1●3 accept rate: 0%
 0 Why is my code results "SIGSEGV" Code is here: http://www.codechef.com/viewsolution/4368543 answered 23 Jul '14, 08:52 56●4 accept rate: 0% 1 @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! :) (23 Jul '14, 09:48) Thanks man :) (23 Jul '14, 09:57)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,482
×1,434
×866
×23
×9

question asked: 14 Jul '14, 15:01

question was seen: 9,138 times

last updated: 15 Jun, 17:16