You are not logged in. Please login at www.codechef.com to post your questions!

×

ABREPEAT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Kamil Debowski
Primary Tester: Marek Sokołowski
Secondary Tester: Praveen Dhinwa
Editorialist: Praveen Dhinwa

DIFFICULTY:

simple

PREREQUISITES:

combinatorics

PROBLEM:

You are provided a string $s$ of length $N$. Suppose $t$ be the string formed by concatenating the string $s$ $K$ times, i.e. $t = s + s + \dots + s$ ($K$ times). We want to find the number of occurrences of subsequence "ab" in it.

Finding number of subsequences "ab" in a given string $s$.

Finding number of subsequences "ab" in a given string $s$ is same as finding number of pair of indices $(i, j), i < j$ such that $s_i$ = 'a' and $s_j$ = 'b'. The brute force way of iterating over all such pairs of indices $i, j$ and checking the conditions $s_i$ = 'a' and $s_j$ = 'b' would be $\mathcal{O}({|s|}^2)$.

However, you can do better. In fact, you can find this in a single pass over the string in $\mathcal{O}(|s|)$ time. Consider an index $j$ such that $s_j$ = 'b', suppose we want to find number of $i$'s such that $i < j$ and $s_i = $ 'a'. It will be same as number of occurrences of character 'a' till position $j$. We can maintain the count of a's by iterating over the array from left to right. This way, we will be able to find the answer in single iteration over the string $s$ in $\mathcal{O}(|s|)$ time. Pseudo code follows.

cnta = 0;
ans = 0;
for i = 1 to |s|:
    if s[i] == a:
        cnta++;
    if s[i] == b:
        ans += cnta;

Can we use this idea directly?

Now we construct the string $t$ and find the number of subsequences "ab" in it in $\mathcal{O}(|t|)$ time, which will be $\mathcal{O}(N \cdot K)$. Constraints of the problem say that $N \cdot K$ could go up to $10^9$. So, this won't work in time.

Towards a counting based solution idea.

Let $t = s_1 + s_2 + s_3 + \dots + s_K$, where $s_i = s$. We call $s_i$ the $i$-th occurrence of string $s$.

Let us view the occurrences of subsequence "ab" in $t$ as follows. One of the below two cases can happen.

  • "ab" lies strictly inside some occurrence of string $s$ in $t$, i.e. "ab" lies strictly inside some $s_i$. We can find the number of occurrences of "ab" in $s$. Let us denote it by $C$. The total number of occurrences "ab" in this case will be $C \cdot K$.

  • In the other case, "a" lies inside some string $s_i$, whereas "b" lies in some other string $s_j$ such that $i < j$. Finding the number of occurrences of "ab" in this case will be same as choosing the two strings $s_i, s_j$ ($\binom{K}{2}$ ways), and multiplying it by the number of occurrences of "a" in $s_i$ (denote by $cnt_a$) and the number of occurrences of "b" in $s_j$ (denote by $cnt_b$), i.e. $\binom{K}{2} \cdot cnt_a \cdot cnt_b$. As $s_i = s$, $cnt_a$ will be number of occurrences of "a" in $s$ and $cnt_b$ will be the number of occurrences of "b" in $s$.

We can find $C, cnt_a, cnt_b$ in $\mathcal{O}(N)$ time. Thus, overall time complexity of this approach is $\mathcal{O}(N)$ which will easily pass in time for $N \leq 10^5$. Pseudo code follows.

cnta = 0
cntb = 0;
C = 0;
for i = 1 to N:
    if s[i] == 'a':
        cnta++;
    if s[i] == 'b':
        cntb++;
        C += cnta;
// First case, i.e. "ab" lies strictly inside some occurences of s, i.e. s_i in t 
ans = C * K 
// The other case, i.e. "a" lies inside some string s_i, where as "b" lies in other string s_j such that i < j
ans += K * (K - 1) / 2 * cnta * cntb ;

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester1
Tester2

This question is marked "community wiki".

asked 23 Apr '17, 20:17

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 24 Apr '17, 01:27

admin's gravatar image

0★admin ♦♦
19.8k350498541


I had a bit of different idea and that is Arithmetic progression. For example, if a string(without repeating) has x number of 'ab' sequences, then that is dependent on position of each 'b' and number of 'a's before it. Let us say the string is 'ababaab'. There are 3 'b' and 4 'a'. The first 'b' has 1 a, 2nd b has 2 a and 3rd b has 4 a. Which comes to a total of 1+2+4 = 7.

Now if we add another string to it the new string becomes 'ababaabababaab'.

The point to be noted is the number of a will be added constantly. So for new b added the values become 1+4 = 5, 2+4 = 6 , 4+4 = 8. Which comes out to 5+6+8 = 19.

Similarly after adding the string 3rd, 4th and 5th time the 'ab' sequences are 31, 43 and 55.

See the pattern yet?

Every time we are adding the string one more time the total sequences increase by 12. it is no. Of a multiplied by no. of b in original string. (Why?)

So if we add string K times then the problem simplifies to finding sum of k elements of a A.P. whose first term is A(no. Of ab sequences in original string) and difference is D(#a * #b).

link

answered 24 Apr '17, 01:56

c0d3_k1ra's gravatar image

2★c0d3_k1ra
175118
accept rate: 11%

I used the same. AP gave a very nice solution to me!

(24 Apr '17, 01:58) vijju123 ♦♦5★
1

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

(24 Apr '17, 20:18) siddharthp5384★
1

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

(24 Apr '17, 20:35) vijju123 ♦♦5★
1

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?

(24 Apr '17, 20:42) siddharthp5384★
1

@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

(25 Apr '17, 00:38) c0d3_k1ra2★

I'll work on this. Thanks :)

(25 Apr '17, 00:45) siddharthp5384★
showing 5 of 6 show all
Answer is hidden as author is suspended. Click here to view.

answered 24 Apr '17, 18:55

marshal_roxx's gravatar image

3★marshal_roxx
(suspended)
accept rate: 2%

edited 24 Apr '17, 18:56

@siddharthp538 -

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.

link

answered 24 Apr '17, 21:41

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 24 Apr '17, 21:44

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.

(24 Apr '17, 21:48) siddharthp5384★
1

I am glad it helped dear :)

(24 Apr '17, 21:52) vijju123 ♦♦5★

@pro1992

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.

link

answered 25 Apr '17, 00:19

arpit728's gravatar image

1★arpit728
6831765
accept rate: 10%

#include<stdio.h>
int main()
{ long long int t,i,j,k,sum,x;
 scanf("%lld",&t);
 while(t--)
 {
  long long int a,b,y;
  scanf("%lld%lld",&a,&b);
    char ch[a+1];
long long int ab[a];
    scanf("%s",ch);
    x=0;
    for(i=0;i<a;i++)
     if(ch[i]=='a')
     {
        ab[x]=0;
       for(j=i;j<a;j++)
       if(ch[j]=='b')
        ab[x]++;

         x++;   
     }


sum=0;   
for(i=0;i<x;i++)
sum=sum+ab[i];


k=b*(b-1)/2;

if(k>0)     
y=b*sum+x*ab[0]*k;  
else
y=sum;  
 printf("%lld\n",y);    
 }
return 0;
}

plss help me w

link

answered 24 Apr '17, 00:57

akshaycs's gravatar image

3★akshaycs
11
accept rate: 0%

edited 24 Apr '17, 00:58

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170

#include <stdio.h>

int main(void){
    int t ;
scanf("%d",&t);
for(int i =0; i<t; i++){<br=""> unsigned long long int n,k;
scanf("%d%d",&n,&k);
char s[n+1];
scanf("%s",s);
int j=0,a= 0,b =0, sum = 0;
while(s[j] != NULL){
if(s[j] == 'a'){
a++;
}
else if(s[j] == 'b'){
sum = sum + a;
b++;
}
j++;
}
unsigned long long int fin;
fin = k*(k-1)/2*a*b+ k*sum;
printf("%llu\n",fin);
}
return 0;
} same solution as of editorial but showing wrong answer.
link

answered 24 Apr '17, 01:37

akash_321's gravatar image

4★akash_321
765
accept rate: 0%

edited 24 Apr '17, 01:46

Fixed formatting...again.

(24 Apr '17, 01:46) vijju123 ♦♦5★

There is a big blunder in your code. Its HERE-

scanf("%d%d",&n,&k);

n and k aren't int, they are usigned long long int. Due to wrong string/format specifier (i.e. "%d") they, n and k were being assigned garbage values.

(24 Apr '17, 01:50) vijju123 ♦♦5★

But still it is showing wrong answer.

(24 Apr '17, 01:56) akash_3214★

Give me time to debug.

(24 Apr '17, 02:04) vijju123 ♦♦5★

correct answer is 5 for this test case not 3.

(24 Apr '17, 02:18) akash_3214★
1

2 'ab' pairs for first 'b' and 3 'ab' pairs for second 'b'. You can verify by trying it in setter's solution.

(24 Apr '17, 02:31) akash_3214★

Yes, i got that. My bad. This is what happens when compres keep you sleep deprived haha XD

(24 Apr '17, 02:36) vijju123 ♦♦5★

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

Reason for error- Overflow caused program to behave unpredictable. and gave error when judge ran it.

(24 Apr '17, 03:14) vijju123 ♦♦5★

Thanks a lot bro..

(24 Apr '17, 03:57) akash_3214★
showing 5 of 9 show all

A simple approach to the problem. Here's my code.

int main() 
{
    int t;
    cin>>t;
    while(t--)
    {
        ll n, k;
        cin>>n>>k;
        string s;
        cin>>s;
        int i;
        vector<int> v(n,0);
        for(i=n-1; i>=0; i++)
        {
            if(s[i]=='b')
            v[i]=1;
            if(i<n-1)
            v[i]+=v[i+1];
        }
        ll sum=0, a=0;
        for(i=0; i<n; i++)
        {
            if(s[i]=='a')
            {
                a++;
                sum+=(v[0]-v[i]);
            }
        }
        ll ans=a*(k*(k+1)*v[0])/2 - sum*k;
        cout<<ans<<endl;
    }
    return 0;
}
link

answered 24 Apr '17, 03:51

shbhm_53's gravatar image

5★shbhm_53
11
accept rate: 0%

My approach is -: Given s - abcb and k=2 ---> (abcbabcb) --->t=s1 + s2

Considering only s, for a the count of b is 2. This will be repeated k times. So , for 'a' in s1 b is k times in s. Similarly for a in s2, k=1 and only 2 b is accounted. Generalizing, it comes down to the formula, (for each a in s) :

sum+=(Cb * k)+(Cb * (k-1)) + (Cb * (k-2)) +.....(Cb * 1);

where Cb is the number of 'b' ahead of given 'a' For given s=abcb and k=2 and 'a' at position 1 : sum+= (2 * 2) + (2 * 1)=4+2=6

But i didnt get correct answers for the last test case, where s=abzbabzbazab and k=80123123 : To summarize my approach, i can break down my formula to this : Count of number of pair of 'ab' in s :-- Cab;

Sum= Cab (k(k+1)/2;=10*(80123123 * 80123124)/2----this does not give me the correct answer.

I cant figure out, what did i miss in here.

link

answered 24 Apr '17, 11:25

vaitan's gravatar image

1★vaitan
11
accept rate: 0%

edited 24 Apr '17, 11:29

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.

(24 Apr '17, 11:40) vijju123 ♦♦5★

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

(24 Apr '17, 14:42) vaitan1★

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.

(24 Apr '17, 14:52) vijju123 ♦♦5★

@vaitan

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.

(24 Apr '17, 15:59) arpit7281★

@vijju123 @dpraveen

Why my solution is not working here is my approach: what I did is I calculated the no. of occurrences of sub-sequence "ab" in s and say it x. Then ans will be ans=x(k(k+1)/2).

link

answered 24 Apr '17, 12:04

arpit728's gravatar image

1★arpit728
6831765
accept rate: 10%

@arpit728 How will you deal with case of-

"baa" repeated twice == "baabaa"

Your x is 0, so your ans reduces to 0, but there are occurances of ab in the final form.

The concept of trailing 'a's has actually given a headache to many. As a hint I will say that there is a A.P. perspective possible to the problem. The number of "ab" formed by a particular a in FINAL string is an AP with common difference = No. of b in original string.

Summing for all a, we get the answer.:)

link

answered 24 Apr '17, 12:51

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 24 Apr '17, 12:52

@vijju123 got your point.

(24 Apr '17, 14:15) arpit7281★

Watch this code

Ezio's Python

Program

t=int(input()) while t>0: count=0 t=t-1 n,k=input().split() n,k=int(n),int(k) a=list(input()) a=a*k for i in range(len(a)): if a[i]=='a': for j in range(i,len(a)): if a[j]=='b': count=count+1 print(count)

link

answered 24 Apr '17, 13:13

ezio27's gravatar image

2★ezio27
316
accept rate: 0%

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;

}

link

answered 24 Apr '17, 15:30

abhi_sarkar96's gravatar image

2★abhi_sarkar96
1
accept rate: 0%

what is wrong with my code ? please help

(24 Apr '17, 15:42) abhi_sarkar962★

I guess it will give TLE.

(24 Apr '17, 15:54) abhi_sarkar962★

Can anyone please explain to me why (k-1)/2 has been multiplied? would not only (K * cnta * cntb) be enough?

link

answered 24 Apr '17, 16:17

pro1992's gravatar image

2★pro1992
1
accept rate: 0%

edited 24 Apr '17, 16:25

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.

(24 Apr '17, 21:42) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×1,173
×891
×83
×8

question asked: 23 Apr '17, 20:17

question was seen: 1,986 times

last updated: 25 Apr '17, 00:45