@vijju123 got your point.
@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.
int main()
{
int t;
cin >> t;
while(t–)
{
unsigned ll n,k,b_count=0,ab_count=0;
cin >> n >> k;
string a,b;
cin >> a;
b=a;
ll i;
for(i=1;i<=k-1;i++)
{
a += b;
}
//cout << a;
for(i=0;i<a.length();i++)
{
if( a[i] == 'b' )
b_count = ( unsigned ll)b_count + 1;
}
for(i=0;i<a.length();i++)
{
if( a[i] == 'b' )
b_count = (unsigned ll)b_count - 1;
else if( a[i] == 'a' )
ab_count = (unsigned ll) ab_count + b_count;
}
printf("%llu",ab_count);
nl;
}
return 0;
}
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.
Can anyone please explain to me why (k-1)/2 has been multiplied? would not only (K * cnta * cntb) be enough?
take a look at this approach …
first we calculate number of b’s after each ‘a’ in the original string and also the total number off b’s in the original string …
eg. let’s take a string abcbabmb … for first “a” , no. of b’s after it’s occurence = 4 and for second “a” , no. of b’s after it’s occurence = 2 .
now , if k==2 , concatenated string will be abcbabmbabcbabmb
for calculating the number of pairs of(a,b) such that index of a<index of b , we can do :-
for each “a” in original string , sum+= no. of b’s after its occurence * (k) + total no. of b’s in original string*( ((k-1)+(k-2)+…+1)=k*(k-1)/2);
sum will be the answer
for code , refer :- http://ideone.com/Div8Ty
3 Likes
@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
If I am not wrong, then c is denoting the number of ‘ab’ sequences in original string.
Your example is very well correct. Your applied concept is correct for that category of test case. But again, that’s just one of the many categories.
You stated that " C here will act as both common diff as well as the first term." . This is wrong. This is a property of this particular string. The common difference actually is number of ‘b’ in the string, and since here number of ‘b’ is equal to number of ‘ab’, you see the equality.
Also, there are some tricky categories of test cases.
One of the categories of the test case are the ones with no ‘ab’ sequence in original string.
Consider string “ba” repeated twice, giving “baba”. Now your c is 0. So if your formula has a multiplication with c, it will give a result 0.
I ran your code for this test case-
Input
1
3 2
baa
Output
1
While I didn’t debug your code (too many variables, made it confusing to see which variable is doing what), I saw that your program prints 1 (if k=2) for strings like “baaa” “baaaaaaa” &etc. I think this will help you find the flaw in logic/code.
What I meant when I said there is an AP perspective, is that, look at the final string.
Let s=“aba” and k=3. Final string (say p) is p= “abaabaaba”
For the very first a in s. It is used to form 1 ab. Also, we can say that p is formed of “aba aba aba” (I inserted a space between repetitions intentionally for clarity). Now look at the starting a of all 3 “aba” and find number of ab subsequence using that particular ‘a’
For 'a' at index 0, ab seq= 3.
For 'a' at index 3, ab seq=2,
For 'a' at index 6, ab seq=1.
I meant that this is an forming an AP. Similarly then I look at ‘ab’ s formed by every ‘a’ present in the string, and sum them up to get the final answer. See that it covers all ‘a’ and hence every possible ‘ab’ is covered, giving correct answer. Some observation and playing with cases/random samples would yield common difference= Number of b in string s, and a= number of ab formed in s by that particular a. Then we can safely apply the AP sum formula to find the answer.
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
If x be the no. of sub-sequence of ab found in s then for each of the k strings would have x no. of sub-sequence ab. and it will contribute total of k*x in final answer.
coming to the second part. now we will consider if we chose ‘a’ from some string i and ‘b’ for some string j.
suppose we chose ‘a’ from the first string then we have cntA choice for picking up ‘a’ and cntB*(k-1) choice for picking up ‘b’ so total pairs of ‘ab’ would be cntA*[cntB*(k-1)] similarly if we choose ‘a’ from the second string then we will have cntB*(k-2) choice for picking ‘b’ and total ‘ab’ pairs in this case would be cntA*[cntB*(k-2)] and so on. The final equation will look like:
ans = cntA*cntB*(k-1)+cntA*cntB*(k-2)+cntA*cntB*(k-3)+…+cntA*cntB*1
Taking cntA*cntB common in above equation we get:
ans = cntA*cntB*[(k-1)+(k-2)+(k-3)+…+1]
where [(k-1)+(k-2)+(k-3)+…+1] is the sum of first (k-1) natural numbers which is given by [k(k-1)/2], so the answer become.
ans=cntA*cntB*[k(k-1)/2]
and then we add the case 1 so the final answer would be:
ans= (k*x)+(cntA*cntB*[k(k-1)/2])
If you are still in doubt then put in comments.
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