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}$ ~v_{2, 1}~ as large as possible, so we should set it to $K-1$ ~K-1~. Since $(v_{2, 1} + v_{2, 2})$ ~(v_{2, 1} + v_{2, 2})~ mod $K = X$ ~K = X~, we may calculate $v_{2, 2} = (X-v_{2, 1})$ ~v_{2, 2} = (X-v_{2, 1})~ mod $K$ ~K~.

Time complexity: $\mathcal{O}(1)$ ~\mathcal{O}(1)~

Subtask 2

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

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

Subtask 3

Again, set $v_{N, 1}, v_{N, 2}, \dots, v_{N, N-1}$ ~v_{N, 1}, v_{N, 2}, \dots, v_{N, N-1}~ to $K-1$ ~K-1~. Set $v_{N, N}$ ~v_{N, N}~ to $0$ ~0~, and construct the pyramid. Notice that if we increment $v_{N, N}$ ~v_{N, N}~ by $1$ ~1~, then $v_{1, 1}$ ~v_{1, 1}~ will also increase by $1$ ~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}$ ~v_{N, N}~ in order for $v_{1, 1}$ ~v_{1, 1}~ to equal $X$ ~X~.

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

Subtask 4

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

If we were to set all numbers in row $N$ ~N~ to $K-1$ ~K-1~, then $v_{1, 1}$ ~v_{1, 1}~ would equal $(-2^{N-1})$ ~(-2^{N-1})~ mod $K$ ~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})$ ~K = ((K-1) \times 2^{N-1})~ mod $K = (-2^{N-1})$ ~K = (-2^{N-1})~ mod $K$ ~K~. Applying the idea from subtask $3$ ~3~, we see that we should increment $v_{N, N}$ ~v_{N, N}~ $(2^{N-1}+X)$ ~(2^{N-1}+X)~ times. Thus, we should 'correct' the value of $v_{N, N}$ ~v_{N, N}~ by setting it to $(2^{N-1}-1+X)$ ~(2^{N-1}-1+X)~ mod $K$ ~K~.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Comments

There are no comments at the moment.