NAddOdd - Topcoder - Single Round Match 714 Round 1 - Division I, Level Two I am interested in DP problems from the past couple of days and am trying to solve various problems on topcoder. To be very frank could not even solve a single one till now. I went through https://community.topcoder.com/stat?c=problem_statement&amp;pm=14408 question and thought to try this. I could come up with a recursive solution easily but now I am struggling for a DP solution. The following is the best I came up with:

package testpackage;

import java.util.HashMap;
import java.util.Map;

public class NAddOdd {

    public static Map&lt;Long, Long&gt; map = new HashMap&lt;Long, Long&gt;();

    public static void main(String[] args) throws Exception{
        System.out.println(solve(1, 1000, 3));
    }

    public static long solve(long L, long R, int K) throws InterruptedException{
        long answer=0l;
        for(long l = R;l&gt;=L;l--){
            answer+=solveInter(l,K);
        }
        return answer;
    }
    public static long solveInter(long h, long K) throws InterruptedException{
        if(map.get(h) != null){
            return map.get(h);
        }
        if(K&gt;=h){
            if(map.get(h) == null)
                map.put(h, 0l);
            return 0l;}
        if(h%2 == 0){
            if(map.get(h) == null)
                map.put(h, 1+solveInter(h/2, K));
            return map.get(h);
        }
        else{
            h = h+K;
            if(map.get(h) == null)
                map.put(h, 1+ solveInter(h, K));
            return map.get(h);
        }

    }

}


But this takes time on bigger values. Also I know memory would fails on large long values. Any clues to perfect this one?

Thanks.
First the minor things about your coding style:


0l should be 0L to avoid confusing it with 01
ALWAYS use brackets after each if/for/while/...
variables are lowerCamelCase by convention. You don't need to copy the question literally. Using single capital letters usually means it's a generic type parameter. It does make sense to use l, r and k here instead of longer more readable names though, since the method is directly related to the given question.
throws InteruptedException can be removed since it's never thrown.
if(map.get(h)==null) is always true after the initial != null check. No need to check that again.
putting something in a map to then taking it out again right after seems silly. Just store it in a temp variable.




There are 2 small optimisations that reduce entries in the map without giving up speed.

The first optimisation is to first check if h is smaller than k and return 0 without storing it.

public static long solveInter(long h, long k) {
    if(h &lt;= k){
        return 0L;
    }
    if(map.get(h) != null){
        return map.get(h);
    }


The second is for odd numbers to also do the following "even" step at the same time like this: map.put(h, 2 + solveInter((h+k)/2, k));

That way, no number larger than R is ever stored.

After a bit of testing it seems a lot more numbers don't need to be stored as well. For example running

public static void main(String[] args) throws Exception{
    System.out.println("total: "+ solve(1000000L, 1001000L, 1001));
    System.out.println("stored entries: " +map.size());
}


shows that this change alone reduces the entries from 15941 to 10962 and this for the total: 19478 steps in the solution.



That's about as much as I can save on your solution without making compromises. If you don't mind giving up a bit of speed to further reduce the number of stored results (to solve the memory issues) you can for example not store any even numbers. This changes the computation from this:

    if(h%2 == 0){
        int result = 1 + solveInter(h / 2, k);
        map.put(h, result);
        return result;
    }

    int result = 2 + solveInter((h + k) / 2L, k);
    map.put(h, result);
    return result;


into this:

    int result = 0;
    while(h%2 == 0){
        if(h &lt;= k) {
            return result;
        }
        result ++;
        h /= 2;
    }

    result = result + 2 + solveInter((h + k) / 2L, k);
    map.put(h, result);
    return result;


This then get's the stored entries in the previous example down to 5730.



I didn't run this on the 4th example
(System.out.println("total: " + solve(1645805087361625L, 9060129311830846L, 74935));)
because those numbers are huge and will take a long time even if you would have a lookup table for all the solveInter results.

I have no idea about how many entries you can store in the map. I did notice that the chains are usually really short. Even for huge numbers like:

System.out.println("total: "+ solve(Long.MAX_VALUE-1, Long.MAX_VALUE-1, 1));


the total is only 66. This is because number goes down logarithmicaly. Even if you have a lot of odd numbers the total will only be 2 or 3 times as large. So to reduce the memory requirements further you could change the map to Map&lt;Long, Short&gt; (32000 will certainly be big enough to store the length of the chain).



Perhaps someone more math minded can come up with some more speed improvements by reducing the required calculations :)