But this dp is still O(N2⋅K). We can optimize this dp, coming to dp[i][j]=dp[i−1][j−1]+dp[i−2][j−1]+dp[i−1][j]. pre-compute this dp for all 1≤n,k≤1000, and we can for fixed N,K sum up all values dp[i][K],K i≤N.
Why? How? Where did this derivation come from?
What I mean to point out is, dont you think its highly weird to just write the recurrence here as “we can optimize this to ___” and skip the part of how we got that? No offence, but I feel skipping of that part shouldnt be done.
This can also be solved fully using divide and conquer with Dynamic programming.
Direction of this approach:-
Break the 2 * n matrix into two halves. Now, (number of ways to fill k bricks in 2 * n matrix) will be equal to (number of ways to fill 0 brick in left half) * (number of ways to fill k tiles in right half) + (number of ways to fill 1 brick in left half) * (number of ways to fill k-1 brick in right half) + …other terms.
Let f(n, k) denote the answer then we have the recurrence
f(n, k) - f(n - 1, k) = f(n -1, k - 1) + f(n -1, k - 2)
Now f(n, 1) = 2n, which is linear, which implies that f(n, 2) must be quadratic, which implies that f(n, 3) must be cubic and so on…
So for fixed k, f(n, k) will be a kth degree polynomial in n, and therefore i precomputed f(n, k) for n, k upto 2000 and then I answered queries in O(n) using Lagrange Interpolation.
Now, consider the number of i length strings consisting of only a/b′s and the number of positions j where a character equals its previous character. We can store this in f(i,j),
f(1,0)=a,b=2
f(i,j)=f(i−1,j)+f(i−1,j−1)
Number of ways = (Number of ways of forming i non-empty groups of k columns) * (Number of ways of placing this i groups around n-k columns) for i=1,2,3…k
Number of ways of forming i groups of k columns = (Number of ways of distributing k objects into i groups) * (2^i)
where in each group alternate bricks of row 1,2 are selected and each group can have two orientation (either first brick is from first row or second)
Thus, Number of ways = sum( (k-1)C(i-1) * 2^i * (n-k+1)C(i) ) for i=1,2,…k
Solved in O(K). The new bricks are arranged in a number of contiguous groups, between 1 and K such groups. For any one such value g of the number of groups, there will be \binom{k-1}{g-1} ways of splitting up the new bricks and \binom{n-k+1}{g} of inserting those groups into the path. Each group can be laid 2 ways of course, left- or right-hand start, so there is also a factor of 2^g.
Then iterate from g=1 up to g=k (or g=n-k+1 if smaller), updating the binomial coefficients stepwise rather than recalculating, using modular inverses up to 1000 which are precalculated.
Still, I feel if we can write a part or explain about something, we shouldnt just assume that anyone familiar with it will get it. The editorial is also for people who are unfamiliar with it and I think it benefits them if explanation is included. A personal opinion though