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

×

CHWLD - Editorial

PROBLEM LINK:

Practice

Contest

Author: Md Shahid

Tester: Arkapravo Ghosh

Editorialist: Md Shahid

DIFFICULTY:

Hard

PREREQUISITES:

Descrete Mathematics, Generating function and Modular Exponentiation

PROBLEM:

Given-

  • $f(0) = 1$
  • $f(1) = 5$
  • $f(n) = 2f(n-1) + f(n-2) + 2^{n-2}$ when $n \geq 2$
you need to calculate all values of $f(i)$ in a range L to R, where $L \leq i \leq R$

QUICK EXPLANATION:

The solution of the given recursive function is $f(n) = 2^n + 3n$. Use modular exponentiation to make your program run within time limit.

EXPLANATION:

This problem belongs to Discrete Mathematics. In the real life scenario, you also have to face such problem where there can be a recursive equation but you can not solve it recursively because recursion can cause your program to execute for a long time, in Competitive programming you will get time limit exceed(TLE) and as a competitive programmer you don't want it right. So here come two techniques to solve this type of problem-

  • Using Generating Function
  • Matrix Exponentiation.
Here, i will talk about how to solve this problem using generating function.

Let $G(x) = \sum_{n=0}^{\infty} a_n x^{n}$ be generating function.
Then $f(n) = 2f(n-1) + f(n-2) + 2^{n-2}$ -------(1) when $n \geq 2$, $f(0) = 1$, $f(1) = 5$

Multiplying both sides of (1) by $x^n$ and summing from $n=2$ to ${\infty}$

$\sum_{n=2}^{\infty} a_n x^n - 2 \sum_{n=2}^{\infty} a_{n-1} x^n + \sum_{n=2}^{\infty} a_{n-2} x^n$ $= \sum_{n=2}^{\infty} 2^{n-2} x^n$
or $G(x) - a_0 - a_1 x -2x(G(x) - a_0) + x^2 G(x) = \frac{x^2} {1-2x}$
Substituting a_0 =1, a_1 = 5
$(1-2x - x^2)G(x) = 1 + 3x + \frac {x^2} {1-2x} $
or $G(x) = \frac {1+x-5 x^2}{(1-2x)(1-x)^2}$
or $ G(x) = \frac {1}{1-2x} - \frac {3}{1-x} + \frac {3}{(1-x)^2}$
or $ G(x) = \sum_{n=0}^{\infty} (2x)^n - 3 \sum_{n=0}^{\infty} x^n +3 \sum_{n=0}^{\infty} (n+1) x^n $
or $ G(x)= \sum_{n=0}^{\infty} (2^n - 3 + 3(n+1)) x^n$
$a_n = 2^n - 3 + 3(n+1) = 2^n + 3n $

$ \therefore a_n = 2^n + 3n$

AUTHOR'S AND EDITORIALIST'S SOLUTIONS:

Author's and editorialist’s solution can be found here.

This question is marked "community wiki".

asked 15 Mar, 12:49

dshahid380_'s gravatar image

3★dshahid380_
314
accept rate: 0%

edited 15 Mar, 12:50

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:

×94
×17
×5

question asked: 15 Mar, 12:49

question was seen: 66 times

last updated: 15 Mar, 12:50