The Question :

Utkarsh being a very talkative child, was scolded by his teacher multiple times. One day, the teacher became very angry and decided to give him a very rigorous punishment. He made him stand on the school field which is X axis.

Utkarsh initially stood at X = 0. The teacher asked him to run to X = N. But, to make the process quick, Utkarsh decided that he will make jumps of 2 or 3 steps only, i.e., from X = S he can jump to X = S+2 or X = S+3.

Utkarsh decided that he will jump 2 steps with probability P/100 and jump 3 steps with probability 1-P/100.

You need to find the probability that he will reach exactly on X = N.

Constraints: 0 < N <= 106 0 <= P <= 100

Input Constraints: The first line contains two integer N and P.

Output Constraints: Your answer must contain exactly 6 digits after the decimal point.

The Solution

I applied DP using memoization using HashMap ,on large input it gives stackoverflow error at hashmap.containsKey line , please tell why it shows that error and a better way to do memoization here . i have faced this problem many times.

import java.util.HashMap;
import java.util.Scanner;

public class Utkarsh_and_Jumps {
    private static double p;
    private static HashMap<Integer, Double> dp;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        p = scanner.nextInt();
        dp = new HashMap<Integer, Double>();
        System.out.println(String.format("%.6g%n", solve(0, n)));

    private static double solve(int i, int n) {
        if (dp.containsKey(i)) {
            return dp.get(i);
        if (i == n) {
            return 1;
        } else if (i > n) {
            return 0;
        double a = solve(i + 2, n) * (p / 100);
        double b = solve(i + 3, n) * (1 - (p / 100));
        dp.put(i, a + b);
        return a + b;

The Input :

29194 14

The Error

Exception in thread "main" java.lang.StackOverflowError
    at java.util.HashMap.hash(HashMap.java:338)
    at java.util.HashMap.containsKey(HashMap.java:595)
    at Utkarsh_and_Jumps.solve(Utkarsh_and_Jumps.java:24)
    at Utkarsh_and_Jumps.solve(Utkarsh_and_Jumps.java:33)

You get the StackOverflowError because the solve method is called recursively too many times for large inputs such as 29194.

The first time you call solve(0, ...), nothing is already computed, so this will recursively call: * solve(2, ...) and then solve(4, ...), and so on until it reaches 29194 *solve(3, ...)and thensolve(6, ...), and so on until it reaches 29194

However, there's a simple trick to avoid all the recursion: iterate backwards. Call solve(n, ...) (yes, this will call solve(n+2) and solve(n+3), but those will finish fast without recurring). Then, call solve(n-1), then solve(n-2), and so on, until solve(0). Notice how this time all recursive calls will finish in one step, as the values will already be computed and available in dp.

So, before your call to solve(0, n), add the following code:

for (int i = n; i >= 0; i--) {
    solve(i, n);

and you will avoid the StackOverflowError.

Here it is in action: http://ideone.com/7Ou8qq

Note that this is the smallest change to your code that I could make to get it to run, so it's more like a hack. Optimally, you would change your algorithm to run in reverse order by default.

| improve this answer | |
  • \$\begingroup\$ thanks but this concern : you wrote "Notice how this time all recursive calls will finish in one step, as the values will already be computed and available in dp."in forward dp (i from 0) then also value will be calculated and used for further query as during solve(i+2) many values can be used in solve(i+3) , so this will also help. \$\endgroup\$ – JSONParser Jul 20 '17 at 10:29
  • 1
    \$\begingroup\$ @UtkarshShukla Yes, the running time will be the same, but iterating backwards will avoid overflowing the stack. \$\endgroup\$ – Cristian Lupascu Jul 20 '17 at 11:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.