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

×

how to solve this equation efficiently?

please help me solve this equation in O(1) or O(logn) time. 1<=n<=10^18

equation:

(n-1) + (n-2)(n-3)/2! + (n-3)(n-4)(n-5)/3! + (n-4)(n-5)(n-6)(n-7)/4! +......+ (n-(n/2))(n-(n/2+1))..(n-(n-1))/(n/2)!

or this eqvivalent combinatric equation

sum of C(n-k,k) for all 1<=k<=floor(n/2)

asked 14 Oct '18, 16:58

sna902055's gravatar image

5★sna902055
425
accept rate: 7%

1

Is n even ??

(14 Oct '18, 18:57) aryanc4035★

not necessary.

(14 Oct '18, 21:13) sna9020555★

Think about what $C(n-k,k)$ looks like in Pascal's triangle. The sums you have are essentially (barring a leading term $C(n,0)$) sums along diagonals of Pascal's triangle $$ \begin{array}{ccccccccc} & & & & {\color{red}1}\\ & & & {\color{green}1} & & {\color{blue}1}\\ & & {\color{blue}1} & & {\color{magenta}2} & & {\color{orange}1}\\ & {\color{magenta}1} & & {\color{orange}3} & & 3 & & 1\\ {\color{orange}1} & & 4 & & 6 & & 4 & & 1\\ \end{array} $$ which turns out to be Fibonacci numbers $$ {\color{red}1}, {\color{green}1}, {\color{blue}2}, {\color{magenta}3}, {\color{orange}5}, \ldots $$ for which you can apply the usual fast techniques for calculating Fibonacci numbers (like matrix exponentiation).

link

answered 15 Oct '18, 02:59

algmyr's gravatar image

7★algmyr
1.2k13
accept rate: 37%

edited 15 Oct '18, 15:17

1

shouldn't the sequence be like 1,1,2,4,..

As for n=4:-it is 3C1+2C2=4?

(15 Oct '18, 11:45) vivek_19982996★
1

Like I wrote, the sum asked about is essentially Fibonacci numbers. However it's missing the leading term $C(n,0)$. Without the leading term the sequence is just Fibonacci numbers minus one: $0,0,1,2,4,7,12,\ldots$.

Compare (python code, implement choose yourself)

[sum(choose(n-k,k) for k in range(1,n//2+1)) for n in range(0,10)]
-> [0, 0, 1, 2, 4, 7, 12, 20, 33, 54]

with

[sum(choose(n-k,k) for k in range(0,n//2+1)) for n in range(0,10)]
-> [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
(15 Oct '18, 15:11) algmyr7★
1

yeah yeah right... :)

(15 Oct '18, 15:47) vivek_19982996★

@algmyr @vivek_1998299 can you help me solve this question? problem link: https://www.hackerrank.com/contests/moodys-analytics-2018-women-in-engineering/challenges/combination-of-digits

i have try lot but did't got correct formula. please help me.

(15 Oct '18, 21:42) sna9020555★

let dp[n] be ans for n

this is recurrence

dp[n]=dp[n-1]+dp[n-2]+1;

dp[2]=1 dp[3]=2

calculate using expo...

link

answered 15 Oct '18, 00:25

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

thank you.. got it.

link

answered 15 Oct '18, 21:38

sna902055's gravatar image

5★sna902055
425
accept rate: 7%

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:

×1,237
×1,176
×868
×42
×23

question asked: 14 Oct '18, 16:58

question was seen: 386 times

last updated: 16 Oct '18, 00:42