1
\$\begingroup\$

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&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<Long, Long> map = new HashMap<Long, Long>();

    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>=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>=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.

\$\endgroup\$
0
1
\$\begingroup\$

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 <= 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 <= 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<Long, Short> (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 :)

\$\endgroup\$
1
  • \$\begingroup\$ InterruptedException was because I was using Thread sleep for checking some elements. Removed that and made a couple of changes. will update the code in a couple of minutes. Doesn't run on forth equation. OutOfMemory error :( \$\endgroup\$ Jun 1 '17 at 17:10
1
\$\begingroup\$

Bugs:

Your method will cache the result for the wrong value if h is odd as you are increasing the value of h (i.e. will your method return 10 for the 16,17,3 example).

// h = h + k; /*<- incorrect*/
if(map.get(h) == null)
    map.put(h, 1 + solveInter(h + k /*<- correct*/, K));
return map.get(h);

The map should be a local variable to a) ensure thread-safety and b) the cached values are only valid for a specific k, subsequent invocations with a different k would currently use the for the new k invalid values.

Performance:

Using Long#numberOfTrailingZeros allows to handle the even case for all trailing zeros at once, which could speed up the calculation for single values. I don't think that caching here is relevant/has positive influence (at least not with a Long->Long map). Possible implementation (approx. 100 times faster for 9060129311830246L,9060129311830846L,74935):

private static int solve(long n, int k) {
    if (n <= k)
        return 0;
    int i = numberOfTrailingZeros(n);
    for (n >>>= i; n > k;) {
        n += k;
        int ntz = numberOfTrailingZeros(n);
        i += 1 + ntz;
        n >>>= ntz;
    }
    int z = numberOfLeadingZeros(n) - numberOfLeadingZeros(k);
    return i - z - (int) (k - (n << z) >> -1);
}

But: An iterative approach is not viable for huge ranges, regardless of which implementation is used (even something basic like adding all the values in the 4. range runs way too long).

Alternative approach:

One possible solution is to calculate the sum (=required steps) for the range (K, N].
The main-idea is to group all values in this range into the two categories with different behavior, even and odd. Each even value requires one step until it gets smaller (n/2) with a remaining range of (K, n/2], each odd value requires two steps until it gets smaller ((n+k)/2) with a remaining range of (K, (n+k)/2]. The sum of the steps in the current range and the total steps required for the two new ranges is the total value of the current range.
As formula we get

sum(n) = (n/2-k/2)*1  // even values, 1 step each
       + (n-k)/2*2    // odd values, 2 steps each
       + sum(n/2)     // remaining range of even values
       + sum((n+k)/2) // remaining range of odd values

To get the result for a range [N, M] we just have to calculate sum(M)-sum(N-1).

Example implementation:

public static long solve(long L, long R, int K) {
    assert (K & 1) != 0 && L <= R;
    Map<Long, Long> cache = new HashMap<>();
    return sum(R, K, cache) - sum(L - 1, K, cache);
}

private static long sum(long n, int k, Map<Long, Long> cache) {
    if (n <= k)
        return 0;
    Long cached = cache.get(n);
    if (cached != null)
        return cached;
    long sum = (n >>> 1) - (k >>> 1) + (n - 1 | 1) - k
            + sum(n >>> 1, k, cache) + sum(n + k >>> 1, k, cache);
    cache.put(n, sum);
    return sum;
}

Further speed-ups can be achieved by using the iterative version if n-k is below a specific threshold and/or using parallel compution.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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