4
\$\begingroup\$

There is a question to basically find the largest sum in an array, such that no two elements are chosen adjacent to each other. The concept is to recursively calculate the sum, while considering and not considering every element, and skipping an element depending on whether the previous element was selected or not.

I understand that this problem requires the use of Dynamic Programming, but doing so still gives me a TLE. Although my code is very similar to the solution code, I cannot figure out why am I getting a TLE (>1.9 seconds). The constraints are given that n >= 1, and so initialising the DP array to 0's shouldn't be a problem in my opinion.

Algorithmically, I think that the two codes below achieve the same task: processing each element, then either considering it in the sum (in this case, the next recursive call is done for the (i+2)th element), or not considering the element in the sum (the next recursive call is done for the (i+1)th element.

Note:

  • vector<int>&B -> denotes the array elements.
  • int K -> denotes the number of elements whose sum is to be taken
  • int N -> total number of elements in the vector.
  • int i -> keep track of which element is currently being processed

Here is my code:

class Solution{
public:
long long dp[1010][510];
long long maxSum(vector<int> &B, int K, int N, int i){
    if (K == 0) return 0;
    else if(i >= N){
        return INT_MIN;
    }
    else{
        if (dp[i][K] != INT_MIN) return dp[i][K];
        dp[i][K] = max(maxSum(B, K, N, i+1), B[i] + maxSum(B, K-1, N, i+2));
        return dp[i][K];
    }
}

long long maximumBeauty(int N, int K, vector<int> &B){
    int i = 0;
    for (int i = 0; i<1010; i++){
        for (int j = 0; j<510; j++){
            dp[i][j] = INT_MIN;
        }
    }
    return maxSum(B, K, N, i);
}
};

and here is the given solution:

class Solution{
public:
long long dp(int i, int j, int N, int K, vector<int> &B,
             vector<vector<long long>> &cache){
    if(j >= K){
        return 0;
    }
    if(i >= N){
        return -1e15;
    }
    if(cache[i][j] != -1e18){
        return cache[i][j];
    }
    cache[i][j] = max((long long )B[i] + dp(i + 2, j + 1, N, K, B, cache),
                      dp(i + 1, j, N, K, B, cache));
    return cache[i][j];
}

long long maximumBeauty(int N, int K, vector<int> &B){
    vector<vector<long long>> cache(N, vector<long long> (K, -1e18));
    long long ans = dp(0, 0, N, K, B, cache);
    return ans;
}
};

I've tried initialising the DP array to different values (such as initialising it with INT_MIN's instead of 0's), but I'm still getting a TLE. Please help me figure out the reason for getting a TLE in the first code, while the second code does not.

EDIT If you want to test the code out and whether it's giving a TLE error, you can try submitting the code here: question-link

\$\endgroup\$
3
  • \$\begingroup\$ @RoToRa added the language as a tag. Thanks. \$\endgroup\$
    – BlazeRod11
    Sep 11, 2023 at 17:33
  • \$\begingroup\$ Just to be clear, you've confirmed that the program produces the result you want, it just doesn't do it as quickly as it needs to? \$\endgroup\$
    – Sara J
    Sep 11, 2023 at 17:58
  • 1
    \$\begingroup\$ @SaraJ Yes. I was solving this question, and the code that I wrote (the first piece of code) is taking longer to execute (>1.9 seconds) as compared to the optimised code (second piece), but I am not able to figure out the reason for the first piece being inefficient. \$\endgroup\$
    – BlazeRod11
    Sep 11, 2023 at 21:45

2 Answers 2

3
\$\begingroup\$

Do the math to fix a bug

INT_MIN is not an appropriate value to return when the end of the array is reached (i >= N). It's not low enough!

Given the constraints:

  • \$1 ≤ N ≤ 1000\$
  • \$1 ≤ K ≤ ceil(N / 2)\$
  • \$1 ≤ B[i] ≤ 10^9\$

The biggest sum could reach \$10^9 * 500 = 500000000000\$.

reachable sum = 500000000000
INT_MIN       =  -2147483648 (in this competition environment)

And given that the code has this:

if (i >= N) return INT_MIN;

This leads to problems. The intention at this point in the code is to stop exploring this branch of computations, because we're off the end of the input array, so no solutions could possibly come out of this.

Consider this valid input:

7 4
1 1000000000 1 1000000000 1 1000000000 1

The only way to pick 4 non-adjacent items is to pick 1 + 1 + 1 + 1 = 4.

The alternative path computed by the code is intended to be 1000000000 + 1000000000 + 1000000000 + IMPOSSIBLE.

But since "IMPOSSIBLE" is actually -2147483648, the program incorrectly computes as the solution 1000000000 + 1000000000 + 1000000000 + -2147483648 = 852516352.

The fix is simple: define const long long IMPOSSIBLE = -1e9 * 500, and use that instead of INT_MIN.

Allocate memory precisely

The program allocates memory for the dp array to hold computation results of sub-problems:

long long dp[1010][510];

The array dimensions don't match well the listed constraints. The numbers look like something I used to lazily pick, thinking along the lines of "that's gotta be enough to save me from off-by-one errors". Later in life I realized it's worth forcing myself to think the math through.

What the program needs at most is really "just":

long long dp[1000][500];

This will force you to think through potential off-by one errors, and realize that the program needs some minor adjustments.

But the main point here is not about the numbers, but about the process. Because by thinking these numbers through, now I'm more aware of any excess, and it turns out to be important: the program allocates a 500k array for every input, regardless of its size.

And as it turns out, replacing the fixed storage with dynamic storage that's just right for the input makes the solution fast enough to pass.

Other notes

I understand that this problem requires the use of Dynamic Programming, but doing so still gives me a TLE.

Yes. Using the right approach is often not enough. It's important to use it the right way, and to avoid wasting memory and unnecessary computations.

I've tried initialising the DP array to different values (such as initialising it with INT_MIN's instead of 0's), but I'm still getting a TLE.

The initial values are important for logical reasons, not the performance. The algorithm needs to be able to decide if a value is unset or not. Given the input constraints, any value that will never be a valid sum, for example -1 would work.

Alternative implementation

Based on the above, and some other minor improvements, this is a slightly cleaner, passing version of your solution:

class Solution {
public:
const long long IMPOSSIBLE = -1e9 * 500;
const long long UNSET = -1;

long long maxSum(int i, int k, int N, vector<int> &B, vector<vector<long long>> &dp) {
    if (k == 0) return 0;

    if (i >= N) return IMPOSSIBLE;

    if (dp[i][k - 1] != UNSET) return dp[i][k - 1];
    
    dp[i][k - 1] = max(maxSum(i+1, k, N, B, dp), B[i] + maxSum(i+2, k-1, N, B, dp));
    
    return dp[i][k - 1];
}

long long maximumBeauty(int N, int K, vector<int> &B) {
    vector<vector<long long>> cache(N, vector<long long> (K, UNSET));
    return maxSum(0, K, N, B, cache);
}
};
\$\endgroup\$
5
  • \$\begingroup\$ Thanks for pointing it out why INT_MIN won't work! Your alternative solution does pass on the portal. I understand why vectors must be used in this question. Just to clarify, the solution with arrays doesn't work because it's an O(500000) loop for every test-case, while the vector initialisation is an O(N*K) loop? Does that make all the difference in this question? \$\endgroup\$
    – BlazeRod11
    Sep 14, 2023 at 8:14
  • 2
    \$\begingroup\$ @BlazeRod11 The bug with the INT_MIN may also contribute to the slowness, because in addition to incorrect final result, the computation continues on more paths before reaching "impossible" conclusion. I have a feeling it should not be significant, but I haven't done the math. As for the 500k memory allocation, and the initialization with a loop, I can easily imagine it makes a difference when there are many small test cases. \$\endgroup\$
    – janos
    Sep 14, 2023 at 9:13
  • \$\begingroup\$ @janos I thought that INT_MIN would be the major factor in increasing the time, as the computed value is massive, resulting in increased number of computations without the calls stopping where they should. I had tried changing just the INT_MIN to IMPOSSIBLE, without the vector implementation, and was still getting TLE. I think that using vector here is the key. \$\endgroup\$
    – BlazeRod11
    Sep 14, 2023 at 10:52
  • \$\begingroup\$ Just asking out of curiosity, I'm assuming that there is no way to get an optimum solution to this using an array instead of a vector? I've got my answer, just trying to understand whether arrays can be made equally efficient in this case. \$\endgroup\$
    – BlazeRod11
    Sep 14, 2023 at 10:55
  • 1
    \$\begingroup\$ @BlazeRod11 If INT_MIN was the major issue, then changing it would be enough to get a passing solution. \$\endgroup\$
    – janos
    Sep 14, 2023 at 11:35
2
\$\begingroup\$

Algorithmically ... the two codes below achieve the same task

No.

    if(i >= N){
        return -1e15;
    }
    if(cache[i][j] != -1e18){

The "given" solution distinguishes between two very small numbers, while yours uses only INT_MIN.


retain order

Your identifiers are very short, single-character. Perhaps that's necessary, based on how the original problem was phrased, fine.

long long maximumBeauty(int N, int K, vector<int> &B){
...
    return maxSum(B, K, N, i);

But don't arbitrarily reorder {N, K, B} to {B, K, N}, that's crazy. Though the machine doesn't care, you're not helping with human cognition.

Copying identifier names was good. But you should have included comments describing the meaning behind each single-character name.


This codebase accomplishes a subset of its design goals.

I would not be willing to delegate or accept maintenance tasks on it.

\$\endgroup\$
1
  • \$\begingroup\$ I agree that arbitrarily reordering the order of the parameters doesn't make any sense. I had to code it in a very short period of time in a coding contest; hence I probably didn't even realise I made my code look this ugly. Thanks for pointing it out! :) \$\endgroup\$
    – BlazeRod11
    Sep 14, 2023 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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