Editorial for Yet Another Contest 5 P1 - Number Pyramid

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Subtask 1

We should try to make v_{2, 1} as large as possible, so we should set it to K-1. Since (v_{2, 1} + v_{2, 2}) mod K = X, we may calculate v_{2, 2} = (X-v_{2, 1}) mod K.

Time complexity: \mathcal{O}(1)

Subtask 2

We should try to make v_{N, 1}, v_{N, 2}, \dots, v_{N, N-1} as large as possible, so we should set them all to K-1. We now need to choose the value of v_{N, N} such that v_{1, 1} = X. It suffices to brute force over all possible values of v_{N, N}, constructing the entire pyramid in order to check if v_{1, 1} = X.

Time complexity: \mathcal{O}(N^2K)

Subtask 3

Again, set v_{N, 1}, v_{N, 2}, \dots, v_{N, N-1} to K-1. Set v_{N, N} to 0, and construct the pyramid. Notice that if we increment v_{N, N} by 1, then v_{1, 1} will also increase by 1, since only the rightmost values in each row of the pyramid are affected. This allows us to easily calculate the number of times we must increment v_{N, N} in order for v_{1, 1} to equal X.

Time complexity: \mathcal{O}(N^2)

Subtask 4

Again, set v_{N, 1}, v_{N, 2}, \dots, v_{N, N-1} to K-1. Observe that the pyramid resembles that of Pascal's triangle. In fact, if we were to multiply each number in row N by the number in the corresponding position in Pascal's triangle, then the sum of those numbers taken modulo K would equal v_{1, 1}. Formally, v_{1, 1} = (\sum_{x=1}^N v_{N, i} \times \binom{N-1}{x-1}) mod K. This can be observed by considering each number in the pyramid algebraically as the sum of multiples of values in row N.

If we were to set all numbers in row N to K-1, then v_{1, 1} would equal (-2^{N-1}) mod K. This is because the sum of each row in Pascal's triangle is a power of two. This can also be proven using the binomial theorem to show that ((K-1) \times \sum_{x=1}^N \binom{N-1}{x-1}) mod K = ((K-1) \times 2^{N-1}) mod K = (-2^{N-1}) mod K. Applying the idea from subtask 3, we see that we should increment v_{N, N} (2^{N-1}+X) times. Thus, we should 'correct' the value of v_{N, N} by setting it to (2^{N-1}-1+X) mod K.

Time complexity: \mathcal{O}(N)


There are no comments at the moment.