×

# STROPR - Editorial

Author: Vasia Antoniuk
Tester: Istvan Nagy
Editorialist: Miguel Oliveira

Easy

Combinatorics

# PROBLEM:

Given an array A of N integers, a position x, and a number M, find the value of $A_x$ after performing the following operation M times:

for i = 2 to N:
A[i] = A[i] + A[i-1]


As the answer could be large, the answer should be given modulo $1\,000\,000\,007$.

# EXPLANATION:

In the first subtask, we have $x \leq 2$. So we only have 2 cases:

• $x = 1$: $A_1$ is never changed in the given procedure, so we already have the result (don't forget the modulo!)
• $x = 2$: in each execution of the above procedure, we add $A_1$ once to $A_2$. So the result is just $A_2 + M \times A_1$.

The second subtask guarantees that $N \times M \leq 10^6$. This means that we can just perform the given algorithm M times. This approach takes $O(N\times M)$ time, which is ok with these constraints.

The number $N$ is irrelevant if larger than $x$ because $A_x$ is only affected by indices smaller than $x$. Hence, I will consider $N=x$ for the rest of the editorial, i.e., we will want to know the value of $A_N$.

When we are given a set of operations to be performed, a good starting point is to see what happens after a few iterations. Suppose we have $N = 5$, and the initial values are $A_1 = a$, $A_2 = b$, $A_3 = c$, $A_4 = d$, and $A_5 = e$.

You may recognise that the factors associated with each initial value are binomial coefficients.

In each step, we are summing the values of a column in the Pascal Triangle. In the above example, $M= 5$, so we are interested in summing the first 5 lines in each column. For example, the value associated with a in the final $A_5$ is the result of $\binom{3}{3} + \binom{4}{3} + \binom{5}{3} + \binom{6}{3} + \binom{7}{3}$.

It can be shown (see here) that $\sum_{m=0}^n{\binom{m}{k}} = \binom{n+1}{k+1}$. In fact, $\sum_{m=0}^7{\binom{m}{3}} = \binom{8}{4} = 70$.

So, we now have a formula to get the coefficient of each initial value, in order to get the final $A_N$. In the above example, we have $A_5 = \binom{M+3}{4} a + \binom{M+2}{3} b + \binom{M+1}{2} c + \binom{M}{1} d + \binom{M-1}{0} e = \\ \binom{8}{4} a + \binom{7}{3} b + \binom{6}{2} c + \binom{5}{1} d + \binom{4}{0} e = \\ 70a + 35b + 15c + 5d + e$

The binomial coefficient can be calculated as $\binom{n}{k} = \frac{n!}{k! (n-k)!}$. M is up to $10^{18}$ so it is too big to calculate the factorial directly. However, we can take advantage of the formula we are calculating.

$\binom{M+3}{4} = \frac{(M+3)!}{4! (M+3-4)!} = \frac{(M+3)!}{4! (M-1)!} = \frac{M * (M+1) * (M+2) * (M+3)}{4!}$

$\binom{M+2}{3} = \frac{M * (M+1) * (M+2)}{3!}$

$\binom{M+1}{2} = \frac{M * (M+1)}{2!}$

$\binom{M}{1} = \frac{M}{1!}$

$\binom{M-1}{0} = 1$

As you can see, we can calculate each factor iteratively using the previous value. In order to divide by each factorial, we need to use the Modular Multiplicative Inverse, which can be computed in $O(\log{N})$. So, the time complexity of this approach is $O(N \log{N})$.

# Sample Solutions

5★mogers
659716
accept rate: 25%

19.8k350498541

 4 In fact, calculating the inversion from 1 to n can be O(n), ... see link text answered 15 Feb '16, 16:19 4★miskcoo 31●1 accept rate: 0%
 3 solution idea for 3 easy problems. https://shadekcse.wordpress.com/2016/02/15/codechef-feb16-challenge/ answered 15 Feb '16, 16:59 3★shadek 109●1●3 accept rate: 0%
 2 @lucky30 , don't find $nCr$ each and every time instead use the value form the previous calculation. answered 15 Feb '16, 15:40 4★bhishma 297●7 accept rate: 11%
 2 The coefficients in the solution are actually the m'th diagonal of the pascal's triangle.. For easier and clear solution, you might want to see My solution: https://www.codechef.com/viewsolution/9374631 answered 15 Feb '16, 18:13 1.1k●1●8 accept rate: 10% Your solution is the same as described in the editorial. (15 Feb '16, 18:51) mogers5★
 1 Nice Editorials! answered 15 Feb '16, 17:50 983●14 accept rate: 11%
 0 Can make that O(n) by calculating coefficients Instantly. https://www.codechef.com/viewsolution/9308756 answered 15 Feb '16, 15:15 11 accept rate: 0% 1 The extra O(log N) factor comes from calculating the modular multiplicative inverse. Your approach is O(N log N). (15 Feb '16, 16:08) mogers5★
 0 Can someone help me in optimizing the code? It gives TLE for subtask 3's test cases. https://www.codechef.com/viewsolution/9425309 answered 15 Feb '16, 15:26 3★lucky30 1 accept rate: 0%
 0 can someone explain about the line For example, the value associated with a in the final A5 is the result of c(3,3)+c(4,3)+c(5,3)+c(6,3)+c(7,3);? how did you obtain this? link This answer is marked "community wiki". answered 20 Feb '16, 16:08 1 accept rate: 0%
 0 For a very Simple Implementation ,refer to this Solution answered 20 Feb '16, 19:05 32●1 accept rate: 0%
 0 Can someone please point out the logical error in my code . this give WA for subtask #2 but passes all of my test cases could be a great help for me https://www.codechef.com/viewsolution/9455251 answered 20 Feb '16, 20:27 1 accept rate: 0%
 0 Can anyone tell me what's wrong with my submission? I keep getting WA on 2 tests of the last sub task. I figured out the coefficient series as (m-1)C(m-1), (m)C(m-1), (m+1)C(m-1), (m+2)C(m-1) .... which is equivalent to the series described in the editorial. I've done extra mods just to be sure although that didn't fix the WAs. Help would be greatly appreciated. Link to submission -Thank You answered 13 Jul '18, 10:27 4★faded4k 26●2 accept rate: 14%
 -2 For an easy implementation, you may refer to My solution. answered 15 Feb '16, 16:25 6★likecs 3.7k●24●81 accept rate: 9%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,875
×3,828
×1,220
×900
×107

question asked: 13 Feb '16, 00:37

question was seen: 5,528 times

last updated: 13 Jul '18, 10:27