0

Just by using the commented code instead of making the recursive calls inside the max function, leads to incorrect result particularly with the following test case

int main() {
    Solution obj = Solution();
    vector<string> arr {"0","11","1000","01","0","101","1","1","1","0","0","0","0","1","0",
                    "0110101","0","11","01","00","01111","0011","1","1000","0","11101",
                    "1","0","10","0111"};
    // output: 17
    cout << obj.findMaxForm(arr, 9, 80) << endl;
    return 0;
}

correct output is 17, but it gives me 14 in that case. Also if you left the take and leave lines uncommentd and just comment the lines of memoization it would output the correct results

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int dfsHelper(vector<string>& strs, int idx, pair<int, int>& target, pair<int, int> curr, int result,
                                                                    vector<vector<vector<int>>>& memo) {
        if (curr.first > target.first || curr.second > target.second) return 0;
        if (idx >= strs.size()) return result;
        if (memo[idx][curr.first][curr.second] != -1) return memo[idx][curr.first][curr.second];

        pair<int, int> addition {0, 0};
        for (char& ch: strs[idx]){
            if (ch == '0') addition.first += 1;
            else addition.second += 1;
        }

//        int leave = dfsHelper(strs, idx+1, target, curr, result, memo);
//        int take = dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo);
//        memo[idx][curr.first][curr.second] = max(leave, take);
        memo[idx][curr.first][curr.second] = max(
                dfsHelper(strs, idx+1, target, curr, result, memo),
                dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo)
                );
        return memo[idx][curr.first][curr.second];
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        pair<int, int> target {m, n};
        vector<vector<vector<int>>> memo(strs.size(), vector<vector<int>>(m+1, vector<int>(n+1, -1)));
        return dfsHelper(strs, 0, target, {0, 0}, 0, memo);
    }
};

actually I have spent hours trying to get the problem here, but this all what I managed to find, I am more leaning to the case that the memoization has some issues, but I can't figure it out

7
  • 1
    actually I have spent hours trying to get the problem here, but this all what I managed to find -- What is a debugger?. Step through the code in a debugger, and determine where the program deviates from what you expected. Second, make sure the code you posted is an actual minimal reproducible example, including headers and a main, just like this. Commented Dec 6, 2024 at 2:26
  • 2
    Does the order of function calls change the result? Function argument evaluation from left to right is not guaranteed. Commented Dec 6, 2024 at 3:05
  • Wait, you posted code that works, and gave instructions to make it fail? Don’t do that. Post code that shows the problem. Commented Dec 6, 2024 at 3:12
  • 2
    What is the code supposed to do? Why is 17 the correct answer? Commented Dec 6, 2024 at 3:13
  • 2
    @MohamedSamir I can't see why these changes that seems equivalent to me -- It is not equivalent. There is no guarantee which argument will be processed first when you called max. The order of evaluation of the arguments is not specified in C++. Maybe your code that outputs 17 just so happens to call the second dfsHelper before the first dfsHelper. Commented Dec 6, 2024 at 12:03

1 Answer 1

2

The reason why you get different results when you do this:

    int leave = dfsHelper(strs, idx+1, target, curr, result, memo);
    int take = dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo);
    memo[idx][curr.first][curr.second] = max(leave, take);

instead of this:

    memo[idx][curr.first][curr.second] = max(
            dfsHelper(strs, idx+1, target, curr, result, memo),
            dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo)
            );

is that in the second set of code, you are calling std::max using the results of dfsHelper, but the order of evaluation of arguments in C++ is not specified. Thus it is more than likely that

dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo)

was evaluated before

dfsHelper(strs, idx+1, target, curr, result, memo)

However, in the code where you are computing leave and take separately, you are always evaluation leave before take.

If you reverse the order of leave and take evaluations, the results will be 17:

int take = dfsHelper(strs, idx+1, target, {curr.first+addition.first,         
                     curr.second+addition.second}, result+1, memo);
int leave = dfsHelper(strs, idx+1, target, curr, result, memo);
memo[idx][curr.first][curr.second] = max(leave, take);

Live Example

So the actual correct code is the one where you are computing leave/take separately, where take is computed before leave.

The code that calls std::max with two calls to dfsHelper, depending on compiler and compiler settings, may or may not work, thus cannot be relied on to give the correct results.

You were just fortunate that std::max(dfsHelper(...), dfsHelper(...)) evaluated the second argument before the first argument.

Sign up to request clarification or add additional context in comments.

3 Comments

Oh, I see! What should I search for to explore more problems like this? Thanks so much for your help—it's truly appreciated!
Well, mostly you pick up these things by experience. There really isn't anything to search for if you aren't aware of this aspect of C++-- you just run into it and then someone informs you of the issue (and then you remember it). Yes, it is in the C++ ANSI specification about this, but how many new programmers would know to look at the specfication, and instead just get stumped by why they get strange answers?
Exactly, Thank you again, Your insight has been really helpful—I truly appreciate you taking the time to share it with me!

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.