Hi,

I'm trying out problem 189A (https://codeforces.me/problemset/problem/189/A). I wrote simple DP (memoization) solution. Upon submission it's giving WA for test case 7

Input

10 3 4 5

Output

275861439

Answer

3

Checker Log

wrong answer 1st words differ - expected: '3', found: '275861439'

Here's my latest submission for the code (the one giving WA): https://codeforces.me/problemset/submission/189/221916967

When I run my code locally with the same failing test case, I get the correct answer. It happened one time before with test case 1 also. Locally, I got correct result, but on submission, it failed. Upon resubmitting with slight change in code (added reference operator '&' in parameter of recursive function, didn't changed the logic), the test case passed and now failing at test case 7.

Pls help in understanding why is this happening, so that I can avoid the mistake (if any) moving further.

I started practicing some DP problems. For some easy problems (like when there's only 1 arg whose value is changing in each recursive call) I'm able to change the memoized solution to tabulated solution. But I'm finding it hard for to do this when there are >= 2 args whose value is changing in each recursive call (and which are not very straightforward). For ex:.

Here's one question from leetcode contest (I hope pasting leetcode link here is not a problem): https://leetcode.com/contest/weekly-contest-359/problems/maximize-the-profit-as-the-salesman/

I was able to write a recursive (and thus memoized solution) but I couldn't figure out how to do it in tabulated form

Here's the memoized solution:

class Solution {
    vector<vector<int>> space;
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        int on = (int)offers.size();
        
        sort(offers.begin(), offers.end(), [&](vector<int>& o1, vector<int>& o2) {
            return o1.at(1) < o2.at(1);
        });
        
        this->space.resize(on, vector<int>(on, -1));
        return max_profit(offers, on, 0, -1);
    }
    
    int max_profit(const vector<vector<int>>& offers, int n, int idx, int prev) {
        if (idx == n) return 0;
        
        if (this->space[idx][prev + 1] != -1) return this->space[idx][prev + 1];
        
        int res = 0;
        if (idx == 0 || prev == -1 || (offers[prev][1] < offers[idx][0])) {
            res = max(res, offers[idx][2] + max_profit(offers, n, idx + 1, idx));
        }
        res = max(res, max_profit(offers, n, idx + 1, prev));
        
        return this->space[idx][prev + 1] = res; 
    }
};

For tabulation, I understand that outer loop should look like this:

for (int i = on - 1; i >= 0; i--) {
}

But I'm not able to understand how to write loop for the prev (inner loop). So far I understand that in tabulation, the prev should look between the i (i.e., from outer loop) and on (i.e., offers.size()).

Is there some blog/video and problems which can help me in getting good and converting memoized solution to tabulated ones ? I'm willing to practice more of these kinds of problem.

(Please comment if anything is not clear in the post.)

Thanks