Problem C - “Jumping Takahashi”

The problem

The original problem is here Given two arrays of length N filled with positive integers: the (A) vector and the (B) vector. We are picking N numbers to compute a sum, each time picking one number either from A or from B. For example, if A is [1,2,3] and B is [4,5,6], we can choose: 1 + 2 + 6 or 4+2+3, etc…

First brute force solution

For each index i, we can choose an integer either from array A or from array B. There is at a maximum $2^n$ solutions.

If we notice that trying to reach X with n numbers is the same than trying to reach X-a or X-b with n-1 numbers,

fn is_possible( jumps: &Vec<(usize, usize)>, index: usize, target: i64) -> bool {

	// Ending the recursion at the final index
	if index == jumps.len() {
		return target == 0;
	}
	let (a, b) = jumps[index];

	// Trying to optimize the choice of the solution looked at first
	return 
		is_possible(jumps, max_sum, min_sum, index + 1, target - a) ||
		is_possible(jumps, max_sum, min_sum, index + 1, target - b);
}

This is pretty elegant and easy to understand. The issue is that the complexity is pretty horrible, as we are looking at $2^n$ choices.

Brute force solution slightly enhanced

Maybe we don’t have to look at all those solutions if we can eliminate wrong solutions earlier.

• If we are looking at a negative target, we can return false already.
• We can compute the sequence where at each index, we choose the smallest number. And the sequence where at each index we choose the largest number. Having those values at each step, we can figure out if the target X is potentially out of reach: if X is less than the remaining sum of minimum, then we will over reach too high. Likewise, if X is bigger than the remaining sum of maximum, we will never reach high enough - so we can eliminate those combinations.

We get then a function a bit more complicated:

fn is_possible(
	jumps: &Vec<(usize, usize)>,
	max_sum: &Vec<usize>,
	min_sum: &Vec<usize>,
	index: usize,
	target: i64
	) -> bool {
	
	if index == jumps.len() {
		return target == 0;
	}

	// Eliminating cases
	if target < 0 {
		return false;
	}
	if index < jumps.len() - 1 &&
		(target < min_sum[index] as i64 || target > max_sum[index] as i64 ) {
		return false;
	}

	let (a, b) = jumps[index];

	return is_possible(jumps, max_sum, min_sum, index + 1, target - a) ||
		is_possible(jumps, max_sum, min_sum, index + 1, target - b);
	}

This is a good solution which is good enough and brings us almost until a perfectly clean solution… almost. We are still 3x TLE short of an acceptable solution…

The answer will lie in Dynamic Programming.

Solution with Dynamic Programming

If we represent all the combinations with a tree, the idea behind dynamic programming is the following:

• Noticing that a lot of tree branches actually examine the same case, the same situation
• Storing some already computed results of a part of the tree, in order to re-use the result without browsing the whole tree.

In this problem we will use the following:

• We store a 2D array with dimensions n and X, and we call it DP
• DP[k][j] will contain true if we can reach the value j in k steps, and false otherwise

Then we can think recursively:

• If we know all the values in a row, i.e. we know DP[k][j] for a given k and all j, we can compute DP[k+1] in the following way:
  • For each j where DP[k][j] is true, we have DP[k+1][j+a] and DP[k+1][j+b] are true as well.
  • In other words, if we can reach in k steps the value j, for the next step we have choices of either a or b, so we can reach j+a and j+b in k+1 steps. s The algorithm becomes then:

let mut DP: Vec<Vec<bool>> = vec![vec![false;x+1];n];

    let (a0,b0) = jumps[0];
    if a0 <= x { DP[0][a0] = true;}
    if b0 <= x { DP[0][b0] = true; }
    for i in 1..n {
        let (a,b) = jumps[i];
        for j in 0..x {
            if DP[i-1][j] {
                // We can go to j in i-1 steps
                if j + a <= x {
                    DP[i][j+a]= true;
                }
                if j + b <= x {
                    DP[i][j+b] = true;
                }
            }
        }
    }

    if DP[n-1][x] {
        println!("Yes")
    } else {
        println!("No")
    }