Good Bye 2017, Problem D

codeforces
dynamic-programming
expectation

#1

Hi community,
I need help on this problem. I went through the editorial but didn’t get it. Can you please take some time to explain the editorial if you get it or any other solution to this problem.


#2

Can you be more specific which part of the editorial was not clear ? Here are few points though.

  • The sequence can contain any number of b’s in the prefix as they won’t contribute to the answer (why ?)

  • The sequence can contain any number of a’s in the suffix followed by a character ‘b’ and so you can use the formula for infinite AGP to solve that.

  • (i + j) \ge k is enough as a terminating condition because the question says you stop when there are at least k “ab” subsequences, so if j \ge k, then you need to terminate immediately as you have already surpassed the count of k.
    The another possibility is that you have enough number of a’s and if even one b is added we will reach the end of formation of the string. So you can add only b or ab or aab and so on. Note that this clearly forms a arithmetic geometric progression if you try to calculate the expected count.
    Solution Link


#3

I think your solution is different from the editorial in codeforces. Please explain the code below which I copied from your solution.

if(prefix_cnt_a + cnt_ab >= k) { //infinite AGP
LL temp = (prefix_cnt_a + cnt_ab) * inverse(p_b);
temp %= M;
temp = temp + (p_a * inverse(((p_b) * (p_b)) % M)) % M;
temp %= M;
return dp[prefix_cnt_a][cnt_ab] = (temp * p_b) % M;
}


#4

Suppose X = prefix\_cnt\_a + cnt\_ab , then if you add one ‘b’ the sequence contains X ab which will be greater than k as per the condition. Now add “ab” then sequence will contain X + 1 ab , add “aab” then sequence will contain X + 2 ab and so on. So the expected value is actually: X * p_b + (X + 1) * p_a * p_b + (X + 2) * p_a ^ 2 * p_b + (X + 2) * p_a ^ 3 * p_b . . . . infinite terms. You can find this sum by taking p_b common and the rest of the expression is simply an AGP. AGP sum for infinite terms is easy to find you can return it as the answer of the base case.

After the completion of recursion, you see that I have performed few operations with the returned answer which was actually not required as the constant that gets multiplied is actually 1 and is the reason behind why there is no affect of adding any number of b’s to the prefix of the string.


#5

Thanks @apptica. I got your solution.