You are not logged in. Please login at www.codechef.com to post your questions!

×

STROPR - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Easy

PREREQUISITES:

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:

Subtask1

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$.

Subtask 2

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.

Subtask 3

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

Author
Tester
Editorialist

asked 13 Feb '16, 00:37

mogers's gravatar image

5★mogers
659716
accept rate: 25%

edited 18 Feb '16, 22:26

admin's gravatar image

0★admin ♦♦
19.8k350498541


In fact, calculating the inversion from 1 to n can be O(n), ... see link text

link

answered 15 Feb '16, 16:19

miskcoo's gravatar image

4★miskcoo
311
accept rate: 0%

link

answered 15 Feb '16, 16:59

shadek's gravatar image

3★shadek
10913
accept rate: 0%

@lucky30 , don't find $nCr$ each and every time instead use the value form the previous calculation.

link

answered 15 Feb '16, 15:40

bhishma's gravatar image

4★bhishma
2977
accept rate: 11%

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

link

answered 15 Feb '16, 18:13

xariniov9's gravatar image

6★xariniov9
1.1k18
accept rate: 10%

Your solution is the same as described in the editorial.

(15 Feb '16, 18:51) mogers5★

Nice Editorials!

link

answered 15 Feb '16, 17:50

dushsingh1995's gravatar image

4★dushsingh1995
98314
accept rate: 11%

Can make that O(n) by calculating coefficients Instantly. https://www.codechef.com/viewsolution/9308756

link

answered 15 Feb '16, 15:15

rsampaths16's gravatar image

5★rsampaths16
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★

Can someone help me in optimizing the code? It gives TLE for subtask 3's test cases. https://www.codechef.com/viewsolution/9425309

link

answered 15 Feb '16, 15:26

lucky30's gravatar image

3★lucky30
1
accept rate: 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

pravin161's gravatar image

2★pravin161
1
accept rate: 0%

For a very Simple Implementation ,refer to this Solution

link

answered 20 Feb '16, 19:05

astr0naut's gravatar image

2★astr0naut
321
accept rate: 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

link

answered 20 Feb '16, 20:27

ankushg07's gravatar image

4★ankushg07
1
accept rate: 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

link

answered 13 Jul '18, 10:27

faded4k's gravatar image

4★faded4k
262
accept rate: 14%

-2

For an easy implementation, you may refer to My solution.

link

answered 15 Feb '16, 16:25

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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