Problem Link
Author: Teja Vardhan Reddy
Tester: Misha Chorniy
Editorialist: Bhuvnesh Jain
Difficulty
MEDIUM-HARD
Prerequisites
Matrix Multiplication, Recurrences, Linearity of Expectation, Probabilities
Problem
You are given a circular which is equally divided into H parts. There are N building placed on the circle at some points, not necessarily distinct. You can start from any point and start shooting within a range of X. All building within the range collapse. You need to find the expected number of buildings which collapses when the probability of starting from any point is given by the following probability distribution:
Explanation
Subtask 1: N ≤ 1000, H ≤ 10000, K ≤ 10
A simple brute force solution which first finds the probability of starting at each point and then simply iterates through each point and finds the number of buildings which are collapsed will work within the required constraints.
The time complexity of the above approach will be O(H * K + N * H) as X = H in the worst case. The first part is for the pre-computation and the next part if for finding the desired number of buildings which are collapsed. The space complexity is O(H).
Subtask 2: N ≤ 50000, H ≤ 1000000, K ≤ 10
All the further subtasks require the knowledge of linearity of expectation and indicator random variables.
Let us define the indicator random variable Y_i. It equals 1 if there is a building at position i else 0. Using this definition, the expected number of building which collapse is:
where the second sum is taken in a circular manner.
Using linearity of expectation (or rearrangement of terms), we can rewrite the above expression as:
where the second sum is again taken in a circular manner.
Since Y_i is defined to be 1 for all points where buildings are present, we can see that outer sum runs for O(N) times in worst case. For the inner sum, we can just maintain a prefix sum for array a and thus find the required sum in O(1).
Using this approach, the time complexity becomes O(H * K + H + N) which is enough to pass this subtask. The space complexity is O(H).
You can see editorialist approach for {1}^{st} two subtasks below.
Full Solution Approaches
Author/Tester Solution: Matrix multiplcation for recurrence solving
The last approach was bad as it required us to calculate the probability of starting at each point which is not possible as H is very large. If carefully observed, the way future a_i are generated is given by a recurrence relation. Don’t confuse by seeing the convolution form in it. 
In case you don’t know how to solve recurrence using matrix multiplication, I suggest you go through this blog before.
In the last approach, we needed to calculate the prefix sum of some given range, for the recurrence relation, in an efficient manner. We can extend our matrix from K * K for normal recurrence to include one extra row which will calculate the prefix sum. Below the idea with a recurrence containing 3 terms. We can generalise it later.
Let recurrence be a_m = c_1 * a_{m-1} + c_2 * a_{m-2} + c_3 * a_{m-3}. As per blog the matrix is given by
To extend it to contain prefix sum as well, the matrix will look like:
Got the idea, we basically store the initial prefix sum as the last value and add the current value to the prefix sum to extend it further. This can be easily extended to higher order recurrences as well.
Using the above idea naively, we can solve the problem in O(N * K^3 * \log{H}), where for every building we use matrix multiplication to calculate the prefix sums. This is enough to pass the {3}^{rd} subtask but not the last one.
To solve the last subtask, we need to look at one important detail of matrix multiplication. Given matrices of sizes (a, b) and (b, c), the complexity for their multiplication is O(a * b * c). We are used to using square size matrices, so we say the complexity is always cubic. In recurrences, the last step involves multiplying the recurrent matrix, (K, K) with the base matrix, (K, 1) which takes O(K^2) complexity instead of O(K^3). This gives us a neat optimisation as follows:
where R is the recurrent matrix ((K+1, K+1) matrix which is described above), B is the base matrix ((K+1, 1) matrix which is described above) and n = 2^{i_1} + 2^{i_2} + \cdots + 2^{i_{\log{H}}}.
An example of above equation is:
Note that the above step now needs O(K^2 * \log{H}) complexity, reducing a factor K from previous one. But we need to precompute the 2^w powers of the recurrent matrix. This can be done in O(K^3 * \log{H}).
Using the above ideas of precomputation and matrix multiplication, the complexity is O(K^3 \log{H} + N * K^2 * \log{H}). This will easily pass all the subtasks.
For more details, you can refer to the author’s or tester’s solution below.
Editorialist Solution: GP Sum of a matrix (Bad constant factor)
The ideas of precomputation and matrix multiplication described above hold in the editorialist solution too.
The solution uses the following idea for finding the prefix sums or recurrence:
So, we need to find the GP (Geometrix progression) sum of a matrix. This is a known problem. If you don’t know about it, you can read similar problem here. But the only problem with this approach is the large constant factor involved. The matrix used to calculate the GP sum of a matrix is twice the size of given matrix, i.e. the matrix used will have size (2k, 2k). Hence, a constant factor of 2^2 = 4 is added to the complexity of the solution which is very hard to deal with. But with some neat observations like some parts of the matrix always retaining particular values, we can reduce the constant factor in the solution too.
I understand the above is a very brief idea of the solution, but in case you have any problem, you can read through the solution and ask any doubts you have in the comment section below.
The time complexity of the approach will be O(4 * K^3 * \log{H} + 2 * N * K^2 * \log{H}). The space complexity will be O(4 * K^2).
Feel free to share your approach, if it was somewhat different.
Extra Tip: Reduce constant factor in modular matrix multiplication
Below is the general code used to calculate matrix multiplication in the modular field:
for i in [1, n]:
for j in [1, n]:
for k in [1, n]:
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod
It can be easily seen that above code uses O(N^3) mod operations. It should be remembered that mod operations are costly operations as compared to simple operations like addition, subtraction, multiplication etc. We observe the following identity:
Above can be easily proved using X = q * mod + r. Using this fact, we can reduce the number of mod operations to O(N^2) in matrix multiplication. Below is the pseudo-code for it:
mod2 = mod * mod
for i in [1, n]:
for j in [1, n]:
c[i][j] = 0
for k in [1, n]:
c[i][j] += a[i][k] * b[k][j] # Take care of overflows in interger multiplication.
if c[i][j] >= mod2:
c[i][j] -= mod2
c[i][j] %= mod
Note that above trick reduces the running time by approximately 0.8-0.9 seconds. Though it is not required for the complete solution, knowing it can always help and might be useful somewhere else.
Time Complexity
O(K^3 \log{H} + N * K^2 * \log{H})
Space Complexity
O(K^3)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Editorialist’s solution for subtask 1 and 2 can be found here.
Editorialist’s solution can be found here.
