BBRICKS - Editorial

combinatorics
dynamic-programming
editorial
oct18

#6

But this dp is still O(N2⋅K). We can optimize this dp, coming to dp*[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*[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.

BTW - Anguepa’s answer here is a very neat explanation of how to derive the recurrence - https://math.stackexchange.com/questions/2945440/number-of-ways-to-select-k-non-adjacent-boxes-in-a-2-times-n-board/2945878


#7

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.

Recurrent relation will look similar to this.

(n, k) = (n/2, 0)(n-n/2, k-0) + (n/2, 1)(n-n/2, k-1) + … + (n/2, k-1)(n/2, 1) + (n/2, k)(n/2, 0)

NOTE: This is not correct relation. Try to think in this direction.

Time complexity of this solution is O(k^2 * log(n)).


#8

I solved it by Lagrange Interpolation

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.

So overall time complexity O(K^2 + TN)

My solution for reference


#9

Can it be solved using Matrix exponentiation?


#10

I also want to know how to do it with Matrix Exponentiation?


#11

Can anyone please explain this part…

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)

#12

Here is my solution (


[1]).
Using Matrix exponentiation.


  [1]: https://www.codechef.com/viewsolution/20553858

#13

@vuvth , can you please explain your approach?
How did you use Matrix Exponentiation for recurrence in two variables?


#14

[Here][1] is my short and simple solution.

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

Extended the logic of single row to two rows :slight_smile:

Time Complexity = O( T . K^2 )
[1]: http://www.codechef.com/viewsolution/20580951


#15

@vuvth plz share your approach. Do mail me at sumeshkpandit@gmail.com


#16

My Python code

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.


#17

It’s simply prefix sum optimization. I think anyone who reads both recurrences properly, will understand that quite easily.


#18

I don’t think so, because K is around 1000, and exponentiating 1000 sized matrices is almost impossible here.


#19

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 :slight_smile:


#20

https://oeis.org/A035597

https://oeis.org/A035598

Basically it is the series Number of points of L1 norm m in cubic lattice Z^n.


#21

this is cool, do you mind explaining your solution ?


#22

I edited that part.


#23

Yes it can be solved using Matrix exponentiation.

Links:

https://discuss.codechef.com/questions/137810/bbricks-editorial?page=1#137989

https://codeforces.com/blog/entry/62610


#24

Yes it can be solved using Matrix exponentiation.

Links:

https://discuss.codechef.com/questions/137810/bbricks-editorial?page=1#137989

https://codeforces.com/blog/entry/62610


#25

Assume T(n) = dp(n, n) * x^n + dp(n, n - 1) * x^(n - 1) + … + dp(n, 0) * x^0

=> T(n) = (x + 1)T(n - 1) + xT(n - 2).

We want dp(N, K) with K <= 1000 so we store first (K + 1) first element of T(n) and calculate on this.

Use Matrix exponentiation

[T(n) T(n - 1)] |(x +1) 1| = [T(n + 1) T(n)]

            |  x    0| 

Cost for multiplication two matrix is O(8 * K ^ 2).

Sorry for my english. Happy coding <3.