CDQU5 - Editorial




Author: Animesh Fatehpuria

Testers: Rajat De Sumit Shyamsukha
Editorialist: Animesh Fatehpuria




Combinatorics , DP.


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)


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:


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.


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 :


After precomputing the answers for each X we can simply print the answers in O(1) Time.


Author’s solution .

To begin with, it’s truly difficult to peruse that without the best possible organizing. I wound up taking it into a program supervisor to inspire it to look more comprehensible. Second, “I’m having issues with this” is not almost enough data to settle the issue. Shine Essay offers Writing Help. Third, you truly shouldn’t request help on what is, to all appearances, a homework issue. Be that as it may, I’ll assume the best about you and disclose to you what I see on first look.

Hey, i’d like to ask you about why top-down won’t work with some modifications:
The modifications were:

  1. I saw where the stackOverflow Exception is occurring , in my computer(locally testing) it was at around when X = 82000.

  2. For this I stored some pre-computed values,
    like this:

  3. I still am getting StackOverflowError when I input 82000.

Even when the input number and stored numbers are so near , Why am i getting that runtime Error?

Same approach I used but getting TLE.

You can use the technique matrix exponentiation to get past even tougher time limits. To know more, watch out errichto’s video about it.