×

# 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●27 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)
 0 I am unable to understand the problem ......for 10001 , 10 1000 , 100 10001 , and 1 are also the substrings ....isn't that ?? answered 24 Oct '14, 17:32 191●5●20 accept rate: 14%
 0 somebody please help, whats wrong with this https://www.codechef.com/viewsolution/14319333 answered 24 Jun '17, 10:54 -1 accept rate: 0% Declare p as long long instead of int. Overflow causing WA (02 Oct '17, 15:07)
 0 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 answered 25 Jul '17, 01:58 1 accept rate: 0% Use long instead of int. Overflow is causing WA (02 Oct '17, 15:06)
 0 can someone tell me what's wrong in this code,thanks in advance. https://www.codechef.com/viewsolution/15359934 answered 17 Sep '17, 12:27 2★rs_710 1 accept rate: 0% Use char s[n+10]. Always give atleast 1 extra space in case you're taking input of string as a char array. (02 Oct '17, 15:05)
 0 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 ? answered 11 Dec '17, 18:17 0★adarshbl 1 accept rate: 0% I have solved this problem now ! I used a different approach ! Thanks ! (12 Dec '17, 00:39) adarshbl0★
 0 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? answered 23 Feb, 20:33 1 accept rate: 0% U can also choose the same index twice so nC2+n=(n*(n+1))/2 (23 Feb, 20:59)
 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:

×13,731
×1,291
×825
×23
×9

question asked: 14 Jul '14, 15:01

question was seen: 7,903 times

last updated: 23 Feb, 20:59