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


AGNSJUMP - Editorial

Agnes Jump

Problem :

Tags: Dynamic Programming, Recursion with memoization.

Author: Shami.

Tester: Murali, Kaustav

This is just an extension of Fibonacci sequence with extra memory and different initial conditions.

How many ways can we get to N? We can reach N from N-1, N-2 and N-3 (those are the allowed step/jump sizes). If we denote number of ways of reaching N by F(N)

                 F(N) = F(N-1) + F(N-2) + F(N-3)

All we need to do now is initialize the values of F(1), F(2) and F(3) (these are given in the examples) and just implement a recursive function.

Let’s examine the order of the algorithm: For each i (1 <= i <= N), we call 3 recursive functions, each of which make another 3 recursive calls. This is asymptotically 3^N for computing N.

For SubTask1, N = 10, 3^10 ~= 6x10^4. T = 10
So total computations are 6x10^5 < 10^7 (you can do roughly 10^7 calculations per second)
This is good enough to pass our time limit of 1s.

For SubTask2, N = 1000. 3^1000 is indeed a large number, so this is not good enough.

But notice that to calculate F(i), we need to calculate F(i-1), F(i-2) and F(i-3) again. And again! This is clearly not needed. Let’s just cache these values.

Let’s take an array of size N and store the number of ways for each i. Take an array of size N and keep storing the values of each i as and when we compute it.

This is a linear order algorithm, so complexity is NT = 10001000 = 10^6.

Now for SubTask3, we have an upper bound on N = 10^6 and T = 10^6. Even with linear algorithm, the complexity is 10^6*10^6 = 10^12. Clearly TLE! Also, a recursive solution may run out of stack depending on the settings.

But we don’t really need to compute F(N) for each T. We can just calculate F(1000000) and store it in an array and just do a plain look up. Complexity is 10^6 + 10^6 = O(10^6).

asked 12 Jan, 15:44

mmmreddy's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 12 Jan, 15:44

question was seen: 69 times

last updated: 12 Jan, 15:44