Help debug dynamic programming problem!

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Recently, I have encounter this dynamic programming problem and I can not debug where I have problem, I used forward DP style and I have checked the transition and base case. Please help me to look at it, I'm so frustrating. Thank in advance.

Problem link: leetcode

My code:

code

#define ll long long
const ll INF = 1e12;
class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(factory.begin(), factory.end());
        sort(robot.begin(), robot.end());
        vector<int> fact;
        for (auto& f : factory)
            for (int i = 0; i < f[1]; i++) fact.push_back(f[0]);

        int n = robot.size();
        int m = fact.size();
        // dp[i][j]: min dist if only fix first (i - 1) robots and use first (j - 1) factories (1-based index)
        vector<vector<ll>> dp(n + 2, vector<ll>(m + 2, INF));
        for (int j = 1; j <= m - n + 1; j++) {
            dp[1][j] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (dp[i][j] != INF) {
                    if (m - j > n - i) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]); // not pick
                    dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(robot[i - 1] - fact[j - 1])); // pick
                }
            }
        }
        return dp[n + 1][m + 1];
    }
};

Updated fix my problem: my for loop only run until i = n, but the final dp state which is dp[n + 1][m + 1] can be reached from dp[n + 1][m] => My for loop should run till n + 1 so this relaxation can happen.

fixed

long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(factory.begin(), factory.end());
        sort(robot.begin(), robot.end());
        vector<int> fact;
        for (auto& f : factory)
            for (int i = 0; i < f[1]; i++) fact.push_back(f[0]);

        int n = robot.size();
        int m = fact.size();
        // dp[i][j]: min dist if only fix first (i - 1) robots and use first (j - 1) factories (1-based index)
        vector<vector<ll>> dp(n + 2, vector<ll>(m + 2, INF));
        for (int j = 1; j <= m - n + 1; j++) {
            dp[1][j] = 0;
        }
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 1; j <= m + 1; j++) {
                if (dp[i][j] != INF) {
                    if (m - j > n - i) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
                    if (i - 1 < n && j - 1 < m) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + abs(robot[i - 1] - fact[j - 1]));  
                }
            }
        }
        return dp[n + 1][m + 1];
    }

Комментарии (6)

Написать комментарий?

frissky9

4 недели назад, # |

← Rev. 2 →

Everything looks great to me but the initialization of dp[1][j] = 0, it should be dp[0][j] = 0 and if you are iterating from (m — n +i > j) you should be returning dp[n][m] try these once.

Edited code

#define ll long long
const ll INF = 1e12;
class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(factory.begin(), factory.end());
        sort(robot.begin(), robot.end());
        vector<int> fact;
        for (auto& f : factory)
            for (int i = 0; i < f[1]; i++) fact.push_back(f[0]);

        int n = robot.size();
        int m = fact.size();
        // dp[i][j]: min dist if only fix first (i - 1) robots and use first (j - 1) factories (1-based index)
        vector<vector<ll>> dp(n + 10, vector<ll>(m + 10
        , INF));
        for (int j = 0; j <= m; j++) {
            dp[0][j] = 0;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = min(dp[i][j], dp[i][j - 1]);
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + abs(robot[i - 1] - fact[j - 1]));
            }
        }
        return dp[n][m];
    }
};

→ Ответить

lvisbl_

4 недели назад, # ^ |

This is actually backward DP, I'm intended to use forward DP, but for this problem backward DP seem more intuitive. Thank you! Btw I have fixed forward DP following phantrongnghia510 suggestion.

phantrongnghia510

← Rev. 3 →

You should consider all valid costs in all final valid states of $$$i$$$: $$$min_j(dp[n + 1][j])$$$ for all $$$j\in [n + 1, m + 1]$$$ since we have just advertised the cost upwards but yet to finalize any optimal cost at $$$dp[i][m + 1]$$$

Thank this is the expected answer, but how do you visualize the problem to get the optimal cost. I think I have "visited" all the states that can reach dp[n + 1][m + 1], and use all those states to "optimize gradually" dp[n + 1][m + 1], hence my expectation that when I reach dp[n + 1][m + 1], it should have been optimized in its optimal cost. But turn out, it is not.

Ah, I finally got it, the state dp[n + 1][m + 1] can be reached from dp[n + 1][m] but my for loop run until i = n then dp[n + 1][m + 1] never be optimized by dp[n + 1][m]. Thank you so much for pointing it out.

orzMorii

sorry for bumping this up again but i have a stupid doubt.

after reading the editorial about flattening $$$factories$$$'s limit of repairs (if factory is on position $$$pos$$$ and can repair $$$limit$$$ robots, just add $$$pos$$$ in our flattened array $$$limit$$$ times) and doing a simple DP on indices,

i tried doing a 3 state $$$DP(i,j,f_{j})$$$ where the last state is just $$$f_{j}$$$ (limit of factory at j index , this does not require flattening like in the editorial). each time we do a $$$repair$$$ transition, mutate the value of $$$f_j$$$ and after computing the value for this transition, for $$$skip$$$ transition, revert back to the original value of $$$f_j$$$.

this did got AC , but shouldn't this cause some sort of side effect or is it okay to mutate state like this and then revert.

$$$ f[j][1] = f[j][1] -1\newline repair = |r[i] - f[j][0] | + F(i+1,j)\newline f[j][1] = f[j][1] +1\newline $$$ $$$ skip = F(i,j+1) \newline DP(i,j,f_{j}) = min(repair,skip) $$$

My Code

       long long dp[101][101][101];
       memset(dp,-1,sizeof(dp));
       std::sort(robot.begin(),robot.end());
       std::sort(factory.begin(),factory.end()); 

       auto r = std::vector<int>(robot.begin(),robot.end());
       auto f = std::vector<std::vector<int>>(factory.begin(),factory.end());
       const int N = r.size();
       const int M = f.size();

       auto F = [&](auto&&F,int i,int j) -> long long {
        if(i == N) return 0;
        if(j == M) return 1e12; // not all robot repaired.
        if(f[j][1]==0) return F(F,i,j+1); // go ahead to next factory

        if(dp[i][j][f[j][1]]!=-1) return dp[i][j][f[j][1]];

        //repair the robot 
        f[j][1]--;
        long long repair = std::abs(r[i] - f[j][0]) + F(F,i+1,j);
        f[j][1]++;

        //skip the factory
        long long skip = F(F,i,j+1);

        return dp[i][j][f[j][1]]=std::min(skip,repair);
       };
       long long answer = F(F,0,0);

PROBLEM LINK

Блог пользователя lvisbl_