Welcome to Codechef Community ! After every contest Codechef releases Editorials ( explanation of the solution to problem ) and makes the submission of others users public( i.e. you can see other people’s code.)
For Editorial check this : ABREPEAT - Editorial - editorial - CodeChef Discuss
Second problem had weird timing problem, it got AC using C string than C++ string object, with C++ string object it causes TLE.
My Solution: CodeChef: Practical coding for everyone
ANSWER=S1+S2.
S1=no. of ab pairs in string s * k
S2:
for this to calculate possible cases are all a’s will take all b’s in s and this can happen in k cases and this cases decreases to 1 eventually so basically
S2=no. of ano. of b(k*(k-1))/2
Plz comment if you did not understand
This problem had a nice use of concept of arithmetic progression (for those with mathematical perspectives).
I used the observations from sample cases to derive it. How did you guys approach the problem? Any other alternate, nice approach?
@vijju123 I used this approach
for(ll i=0;i< n;i++)
{
if(s[i]=='a')
{
ca++;
}
else if(s[i]=='b')
{
cb++;
m=m+ca;
}
}
ll ans=m*k+(ca*cb*k*(k-1))/2;
cout<< ans<< endl;
I don’t know whether it is nice or not but this came tp my mind
1 Like
I used diff idea than your’s
Fixed the format. BTW, can you explain what you are trying to do? I am unable to understand “ll ans=m x k+(ca x cb x k x(k-1))/2;”
consider string s= abcb and k=x
so the string becomes S=s1+s2+s3+…+sx
now first i calculate ab’s in s and this repeats k times therefore count is no. of ab * k
then all “a”'s in s1 can use all the “b”'s in s2 and s3…sx
which gives a count of no. of “a”* no. of b’s * k
next all “a”'s in s2 can use all “b”'s in s3,…sx which gives a count of
no. of “a” * no. of “b” * (k-1)
continue like this …
we come to an end with formula
answer=no. of ab in s * k+ no. of “a” *no. of “b” * k *(k-1)/2.
1 Like
I also used a similar approach. The concepts are same. Thanks for sharing
Sorry for my english I might have frustrated you but this is first time i am using forum so little excited
1 Like
CodeChef: Practical coding for everyone I used this, little different idea than in editorial, I updated the link,
1 Like
Thanks for the link. I think saisurya also did something similar. What was your thinking? Meaning, what trick you found in the question which made you take that approach?
For me it was presence of an AP with d=Number of 'b’s in the string.
pairing of ‘a’ in string i with ‘b’ of string j such that j>i and if i==j then consider only those b which is on the right of ‘a’, through this I got this formula, bk(k-1)/2 + tempb and used this formula on each ‘a’
And then adjust it for k times repeat. Nice.
the idea was too complicated though
1 Like