2 ‘ab’ pairs for first ‘b’ and 3 ‘ab’ pairs for second ‘b’.
You can verify by trying it in setter’s solution.
1 Like
Yes, i got that. My bad. This is what happens when compres keep you sleep deprived haha XD
Got AC for your code. You are suffering from overflow.
Changed-
int j=0,a= 0,b =0, sum = 0;
to
long long int j=0,a= 0,b =0, sum = 0;
Link- CodeChef: Practical coding for everyone
Reason for error- Overflow caused program to behave unpredictable. and gave error when judge ran it.
Thanks a lot bro…
If we repeat “aba” 2 times, it becomes abaaba. Your formula gives answer as-
Sum = 1 x (2 x 3/2)= 3. (If I get your approach correctly) and hence your code fails. Try to account of trailing 'a’s in the end.
@vijju123 Forgor to mention that…i added a case for the last character, if it is ‘a’. For those case it works fine.
I did not understand why my test case 3 fails.
Did you account for existance of “ba” type of strings? I think they are getting neglected. Check my answer for @arpit728 below. I think the same fault is here too.
what is wrong with my code ?
please help
I guess it will give TLE.
I also tried the same approach, the problem is that it won’t work for trailing a’s. try the case ‘baa’ according to your approach this will give ans will be zero.
@vijju123 Did you use sum of an AP formula? If yes then how your ans for 4th sample test case is 64197148392731290 It should be 32098574196365645…I think so. Let me explain for string abzbabzbazab here according to the given code above c will be 10 and since c will be added 80123123(every time incrementing by 10),so now lets apply the formula. Here, a=10,d=10,no of terms=80123123…Applying ap formula ans comes 32098574196365645 and not the given one…Obviously this method is wrong but will you please explain why?
1 Like
@siddharthp538 , look at my code. I use sum of AP formula, and i got correct output.
I think those numbers you stated are for the first a. I then went to the next a did the same. My a=number of ‘b’ after that particular ‘a’, d is 10 for all and number of terms is k. Summing it over for all a I got the answer.
1 Like
Thanks vijju, I appreciate that.But what’s wrong with my one. Suppose given string is abb. Then C is 2,now consider your k to be 3.Final string will be abbabbabb. Here final ans will be 2+4+6…so your C here will act as both common diff as well as the first term. Applying ap formula we do get 12. But this didn’t work with 4th sample test case…Why?
1 Like
It is coming from the fact that there are nC2 ways of choosing a ‘a’ and a ‘b’ to form ‘ab’ by that method. And nC2 is nothing but n(n-1)/2.
Wow! Thanks man! You are really a great person @vijju123 
Actually the test cases which you gave cleared it all. Again Thanks
I am really sorry for being so silly.
I am glad it helped dear
1 Like
@siddharthp538 d = number of As * number of Bs. for 4th sample the D you have taken is wrong, the D = 20 = 4 * 5(Why? I leave this as an exercise for you to find out).
((2 * 10 + 80123122 * 20) * 80123123) / 2 = 64197148392731290
1 Like
I’ll work on this. Thanks
#include <bits/stdc++.h>//authored by abhijay mitra
#define ll long long int
#define N 200001
#define M 1000000007
#define f(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i–)
#define po pop_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define cot cout.tie(0)//solved in time complexity o[n]
using namespace std;int l[N];
#define watch(x) cout << (#x) << " is " << (x) << endl
int main(){
ibs;cti;
int T;
cin>>T;
while(T–){
ll n, k;char c;int last_b=INT_MIN,j=0;int count=0;
cin>>n>>k;int count_a=0,count_b=0;
std::vector v;bool x=0;
for (int i = 0; i < n; ++i)
{
cin>>c;
if (c==‘a’)
count_a++;
if (c==‘b’){
count_b++;
if (x)
{
l[count]=j-last_b-1;
}else{
l[count]=j;x=1;
}
last_b=j;
count++;
}
if (c==‘a’||c==‘b’){
v.pb©;j++;
}
}
for (int i = 1; i <= count; ++i){
l[i]+=l[i-1];
}
ll sum_in_s=0;
for(int i=0;i<count;i++)
sum_in_s+=l[i];
cout<<sum_in_sk+k(k-1)count_acount_b/2<<"\n";
}
return 0;
}