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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

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

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

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_, история, 4 месяца назад, По-английски

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_
4 месяца назад
1

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

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

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_
4 месяца назад
6