PROBLEM LINKS:
Author: Animesh Fatehpuria
Testers: Rajat De Sumit Shyamsukha
Editorialist: Animesh Fatehpuria
DIFFICULTY:
SIMPLE
PREREQUISITES:
Combinatorics , DP.
PROBLEM:
Given a number X , output the total number of ways one can score a score of X by hitting only Cannon and In-Off shots. A cannon shot gives 2 points and an In-Off shot gives 3 points.
Since the answer can be very large, Output the answer MOD 1000000009(10^9+9)
EXPLANATION:
The best way to approach this problem would be through DP and by using memoization.
Before we talk about that , let’s look at a naive recursive approach:
Let us define a function f(x) which represents Number Of Ways to get a Score Of X.
The Important observation is:
f(x)=f(x-2)+f(x-3);
After having identified the recursive algorithm , we must identify the base cases:
This is really simple :
A score of 2 can only be achieved in one way by hitting a cannon and a score of 3 can only be achieved in one way by hitting an In-Off.
A score of 1 and 0 cannot be achieved.
The problem with using Recursion to solve this problem is that there will be many OverLapping Subproblems and it will be tremendously inefficient for large VALUES of X.
The Time Complexity of this approach would be O(2^X) which is not feasible at all.
OPTIMIZATION
We would use memoization (without recursion)(Iterative Bottom Up DP) to drastically reduce the Time Complexity to O(N).
Memoization requires Creating An Array of Size 10^6+1 .
Each Position Y in the Array would denote the answer for X=Y.
We would precompute the answers for each value Y where 1<=Y<=1000000 and then answer each query in O(1) Time.
We know that Array[0]=Array[1]=0 and Array[2]=Array[3]=1 .
Following values from 4 to 10^6 would use the relation :
Array[i]=(Array[i-2]+Arrays[i-3])%(10^9+9);
After precomputing the answers for each X we can simply print the answers in O(1) Time.