You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 14 Jul '14, 15:01

devuy11's gravatar image

4★devuy11 ♦♦
46273842
accept rate: 0%

edited 14 Jul '14, 15:23

nC2 = n*(n-1)/2

(23 Jul '14, 09:07) torqueomega3★

Answered the queries as requested.

(02 Oct, 15:07) vijju123 ♦5★

link

answered 14 Jul '14, 21:24

subham_pasari's gravatar image

2★subham_pasari
-104238
accept rate: 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 <climits>. can a int variable hold this much of value?? try long long datatype for holding everything...

link

answered 14 Jul '14, 22:25

sayaksan's gravatar image

4★sayaksan
264
accept rate: 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)

link

answered 15 Jul '14, 14:21

siddharth93's gravatar image

1★siddharth93
46113
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 <iostream>

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;

}

link

answered 15 Jul '14, 16:19

ajaydwivedi36's gravatar image

2★ajaydwivedi36
-4124
accept rate: 0%

edited 15 Jul '14, 16:20

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

answered 16 Jul '14, 14:16

ankitsablok89's gravatar image

2★ankitsablok89
1223
accept rate: 0%

edited 16 Jul '14, 14:16

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

link

answered 17 Jul '14, 20:36

dorsatum's gravatar image

2★dorsatum
11
accept rate: 0%

1

Change int to long long

(17 Jul '14, 20:49) achaitanyasai5★

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) shivam2174★

@shivam217, thank you!

(18 Jul '14, 13:06) dorsatum2★

@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.

link

answered 18 Jul '14, 13:46

the65bit's gravatar image

4★the65bit
1.1k101327
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; }

link

answered 21 Jul '14, 16:22

rahul1995's gravatar image

2★rahul1995
13113
accept rate: 0%

Why is my code results "Time Limit Exceeded" Code is here: http://www.codechef.com/viewplaintext/4298438

link

answered 21 Jul '14, 16:25

rahul1995's gravatar image

2★rahul1995
13113
accept rate: 0%

Why is my code results "SIGSEGV" Code is here: http://www.codechef.com/viewsolution/4368543

link

answered 23 Jul '14, 08:52

miamiheat's gravatar image

1★miamiheat
564
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) i_am_what_i_am6★

Thanks man :)

(23 Jul '14, 09:57) miamiheat1★

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

link

answered 24 Oct '14, 17:32

nickzuck_007's gravatar image

3★nickzuck_007
191518
accept rate: 14%

somebody please help, whats wrong with this

https://www.codechef.com/viewsolution/14319333

link

answered 24 Jun, 10:54

kamalneel's gravatar image

3★kamalneel
-1
accept rate: 0%

Declare p as long long instead of int. Overflow causing WA

(02 Oct, 15:07) vijju123 ♦5★

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

link

answered 25 Jul, 01:58

highvibes's gravatar image

2★highvibes
1
accept rate: 0%

Use long instead of int. Overflow is causing WA

(02 Oct, 15:06) vijju123 ♦5★

can someone tell me what's wrong in this code,thanks in advance. https://www.codechef.com/viewsolution/15359934

link

answered 17 Sep, 12:27

rs_710's gravatar image

3★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.

AC soln- https://www.codechef.com/viewsolution/15583470

(02 Oct, 15:05) vijju123 ♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×11,590
×1,049
×777
×22
×7

question asked: 14 Jul '14, 15:01

question was seen: 6,028 times

last updated: 02 Oct, 15:07