April cook

help
1

This was my first contest and so I want to check solution of second problem.Any help?

1 Like
2

Please wait for editorials.else u can check other’s solution.

3

Hey you can always check editorial here and also visit the contest page…they are available.

4

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 : https://discuss.codechef.com/questions/96597/abrepeat-editorial

5


here it is

6

Thank you.

7

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: https://www.codechef.com/viewsolution/13381425

8

Thank you.

9

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

10

Hey,

The Editorial : https://discuss.codechef.com/questions/96597/abrepeat-editorial

Cheers!

1 Like
11

got accepted with C++ string

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

1 Like
12

I used diff idea than your’s

13

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?

14

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

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;”

16

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
17

I also used a similar approach. The concepts are same. Thanks for sharing :slight_smile:

18

Sorry for my english I might have frustrated you but this is first time i am using forum so little excited :slight_smile:

1 Like
19

https://www.codechef.com/viewsolution/13381425 I used this, little different idea than in editorial, I updated the link,

1 Like
20

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.