Записи в блоге

№	Пользователь	Рейтинг
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

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

Help solving Floyd Warshall algorithm

Автор lvisbl_, история, 2 недели назад, По-английски

Recently, I have encountered this Floyd Warshall problem, that the problem adds extra constraint on the shortest path (all edge weights + 1 largest vertice on the path). Following my understanding, Floyd Warshall is dynamic programming and when we "relax" the state, I will add that extra condition.

So, I call dp[i][j][k]: the min distance between i and j vertices, and the middle vertices consisting only the first k vertices. And maxCost[i][j][k] is the max cost vertice of the path I have chosen in dp[i][j][k]. So my transition:

if (dp[i][j][k] + maxCost[i][j][k] > dp[i][k][k — 1] + dp[k][j][k — 1] + max(maxCost[i][k][k — 1], maxCost[k][j][k — 1]) or if the last chosen path for two vertices i and j has larger cost for the path for i, j and k is in the middle of the path, then I relax distance between i and j, and set new maxCost for that path. But there is problem with this logic can you help to point it out. Thank!

Code

int n, r, q;
const int mxn = 85;
int dp[mxn][mxn][mxn];
int cost[mxn];
int maxCost[mxn][mxn][mxn];
int test = 1;
void solve() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                dp[i][j][k] = IINF;
                maxCost[i][j][k] = -1;
            }
        }
    }
    for (int i = 1; i <= n; i++) cin >> cost[i];
    for (int i = 1; i <= n; i++) {
        dp[i][i][0] = 0;
        maxCost[i][i][0] = cost[i];
    }
    for (int i = 0; i < r; i++) {
        int u, v, w; cin >> u >> v >> w;
        int newMaxCost = max(maxCost[u][u][0], maxCost[v][v][0]);
        if (dp[u][v][0] + maxCost[u][v][0] > w + newMaxCost) {
            dp[u][v][0] = dp[v][u][0] = w;
            maxCost[u][v][0] = maxCost[v][u][0] = newMaxCost;
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i][j][k - 1] != IINF) {
                    if (dp[i][j][k] + maxCost[i][j][k] > dp[i][j][k - 1] + maxCost[i][j][k - 1]) {
                        dp[i][j][k] = dp[i][j][k - 1];
                        maxCost[i][j][k] = maxCost[i][j][k - 1];
                    }
                }
                if (dp[i][k][k - 1] != IINF && dp[k][j][k - 1] != IINF) {
                    int newMaxCost = max(maxCost[i][k][k - 1], maxCost[k][j][k - 1]);
                    if (dp[i][j][k] + maxCost[i][j][k] > dp[i][k][k - 1] + dp[k][j][k - 1] + newMaxCost) {
                        dp[i][j][k] = dp[i][k][k - 1] + dp[k][j][k - 1];
                        maxCost[i][j][k] = newMaxCost;
                    }
                }
            }
        }
    }
    
    cout << "Case #" << test++ << nline;
    for (int m = 0; m < q; m++) {
        int u, v; cin >> u >> v;
        if (dp[u][v][n] != IINF) cout << dp[u][v][n] + maxCost[u][v][n] << nline;
        else cout << -1 << nline;
    }
    cout << nline;
}

Полный текст и комментарии »

floyd-warshall

lvisbl_
2 недели назад
9

Help debug dynamic programming problem!

Автор lvisbl_, история, 4 недели назад, По-английски

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];
    }

Полный текст и комментарии »

dynamic programming

-2

lvisbl_
4 недели назад
6

Weird overflow behavior of min(a,b) function

Автор lvisbl_, история, 6 недель назад, По-английски

Recently I have done 711C - Coloring Trees, and I have found an overflow when I use min(a,b) function. More specifically, if I use:

min(a, b + c) when a, b and c are long long and sum of b + c large than 32-bit integer then the sum b + c will be treated as 32-bits integer and hence the overflow.

but let say, if I use a temporary variable:

long long tmp = b + c

then

min(a, tmp) will not overflow

What kind of behavior is this?

This is two submissions, one is overflow and the another one use a temporary variable will not overflow:

Overflow: 285989412

Not overflow: 286024512

Полный текст и комментарии »

lvisbl_
6 недель назад
2

[Question] — The combining of both forward and backward DP in a single problem

Автор lvisbl_, история, 5 месяцев назад, По-английски

Recently, I encounter this 1741E - Sending a Sequence Over the Network that combine both forward and backward DP style, that make me feel surprised. I thought that we could only use either forward and backward DP in a problem to solve it. But in this problem we use both? Let call dp[i] is can we separate array from [1,i] into valid segments. Then:

The backward DP: if from range [1,i] we can not separate array into valid segments then we try to make the current number at index i as the length of the last segment => Check backward the range [1,i — b[i] — 1].

The forward DP: if we can separate array into valid segments in range [1,i-1], then the current number at index i can possibly length of the next segments => Update dp[i + b[i]] = true.

The doubt is can I combine both forward and backward DP style in all DP problems? If not, in what case/what type of DP properties the combination of forward and backward style will work? Do we have any related problems that require to combine both styles like this?

Thank in advance.

Полный текст и комментарии »

dynamic programming

-1

lvisbl_
5 месяцев назад
1

[Question] Get TLE when switch the dimension of the DP array

Автор lvisbl_, история, 5 месяцев назад, По-английски

Hello mates, I'm trying to solve this DP question Coin Combinations II from CSES: https://cses.fi/problemset/task/1636/

Initially, I define an array dp[i][j]: meaning number of ways to form sum i, starting choosing coins from j-th index. And this solution using this DP array get me TLE.

But if I switch the two dimension, array dp[i][j]: number of ways to form sum j, starting choosing coins from i-th index. This solution give me accepted. But why?

Note:

Two solution is 99% the same the only different is that I switch two dimensions.
Sum i at most 10^6 and there are at most 10^2 coins.

Thank in advance.

Accepted code

#include<bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
void IN_OUT() {
#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
}
/*--------------------------------------------------------------------------------------------------------------------------*/

const int MOD = 1e9 + 7;

const int mxn = 1e2 + 5;
const int mxx = 1e6 + 5;
int a[mxn];
int dp[mxn][mxx]; // dp[i][j]: number of ways to form sum j, starting choosing coins from i-th index
int n, x;
void solve() {
    cin >> n >> x;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        dp[i][0] = 1;
    }
    
    for (int j = n - 1; j >= 0; j--) {
        for (int i = 1; i <= x; i++) {
            dp[j][i] = dp[j + 1][i];
            if (i >= a[j]) {
                dp[j][i] += dp[j][i - a[j]];
                dp[j][i] %= MOD;
            }
        }
    }

    cout << dp[0][x] << "\n";
}

int main() {
    fastio();
    IN_OUT();
    solve();
    return 0;
}

TLE code

#include<bits/stdc++.h>
using namespace std;
 
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
void IN_OUT() {
#ifndef ONLINE_JUDGE
freopen("Input.txt", "r", stdin);
freopen("Output.txt", "w", stdout);
#endif
}
/*--------------------------------------------------------------------------------------------------------------------------*/
 
const int MOD = 1e9 + 7;
 
const int mxn = 1e2 + 5;
const int mxx = 1e6 + 5;
int a[mxn];
int dp[mxx][mxn]; // dp[i][j]: number of ways to form sum i, starting choosing coins from j-th index
int n, x;
void solve() {
    cin >> n >> x;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        dp[0][i] = 1;
    }
    
    for (int j = n - 1; j >= 0; j--) {
        for (int i = 1; i <= x; i++) {
            dp[i][j] = dp[i][j + 1];
            if (i >= a[j]) {
                dp[i][j] += dp[i - a[j]][j];
                dp[i][j] %= MOD;
            }
        }
    }
 
    cout << dp[x][0] << "\n";
}
 
int main() {
    fastio();
    IN_OUT();
    solve();
    return 0;
}

Полный текст и комментарии »

dynamic programming

lvisbl_
5 месяцев назад
6