CSUB - Editorial

It could be something like this…

nC1= combinations taken 1 at a time; or individual 1’s are their own start and end point.
Then nC2 = combinations taken 2 at a time.
Adding these two makes up nC1+nC2=n×(n+1)/2

But I think it should be someting like this…
Example: 111
nC1= 1,1,1
nC2=11,11,11 we can’t include last combination in this sequence because only way to move is forward and last sequence groups last index and first index together.

So nC2 is here actually nC2 - 1 combination = 11,11
Now the last one is
nC3 = 111

So total numbers in the list are 111,11,11,1,1,1

So we have 6 numbers which satisfy this condition.
And n×(n+1)/2 is actually 6.

I am not entirely sure on this…
If you guys have any other explanation please share.

Shouldn’t the answer for Case #2 (i.e.10001) be 4. the sub-strings being 11,101,1001,10001,
instead of 3?

@kalpaj12 what you’re saying is called subsets and not substrings. A substring is a contiguous sequence of characters within a string. so, here the valid substrings would be {1}(1st element of array),{1}(last element of array),{1,0,0,0,1}. Hence, Answer will be 3

thanks @shinchan6599

Hi,

I am getting WA. Following is my code. I followed the n(n+1)/2 principle, yet I am not able to clear it.
Kindly point out the mistake.

#include <bits/stdc++.h>

using namespace std;


int main(){
	int t, n, count;
	string tmp;
	cin>>t;
	while(t--){
		cin>>n;
		count = 0;
		cin>>tmp;
		for(string::iterator i = tmp.begin(); i!=tmp.end();++i){
			if(*i=='1'){count++;}
		}
    cout<<(count*(count+1))/2<<endl;
	}
	return 0;
}

@insoumniac hope this helps,

first string: 1111
possible ways of getting string of ‘1’ length = 4(length of string)
possible ways of getting string of ‘2’ length = 4-1 = 3(length of string - 1)
possible ways of getting string of ‘3’ length = 4-2 = 2(length of string - 2)
possible ways of getting string of ‘4’ length = 4-3 = 1(length of string - 3)

We sum the ways: 1+2+3+4 = 10(sum of first 4 numbers)

I guess you saw the pattern and how the formula came

1 Like

I am not getting corrct solution.Please check the answer.
#include
#include
using namespace std;

int main() {
// your code goes here
int t,i,j,n,count=0,p,a,k=1;

string b=to_string(k);   

``cin>>t;

for(j=1;j<=t;j++)
{
cin>>n;
cin>>a;
string s=to_string(a);

for (i = 0; i < n; i++) {
if (s.substr(i,1) == b) {
count++;
}
}

   p=(count*(count+1))/2;
    printf("%d\n",p);

}
return 0;
}

Change int to long long

1 Like

achaitanyasai , thank you for looking into this. I did change it, this is the new solution:CodeChef: Practical coding for everyone

Still WA

@dorsatum change flag to long long… link to AC – CodeChef: Practical coding for everyone

1 Like

@shivam217, thank you!

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:

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- CodeChef: Practical coding for everyone

Use long instead of int. Overflow is causing WA

1 Like

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

1 Like

Answered the queries as requested.

I have solved this problem now ! I used a different approach ! Thanks !

U can also choose the same index twice so nC2+n=(n*(n+1))/2