ENAMINE1's blog

By ENAMINE1, history, 4 weeks ago, In English

This is the code for finding whehther there exists a subset equal to the given sum or not?

The interesting part is that when i change the oreder of rec() in return dp[idx][left_sum] = rec(v,idx+1,n, left_sum) | rec(v, idx+1, n, left_sum — v[idx]); i get different result.

Thanks for looking into it in advance.❤️

here is the test case i have attached

100 5142

57 68 27 100 69 49 100 51 71 63 77 20 63 4 11 31 21 23 94 5 56 54 15 88 61 89 5 22 83 55 90 39 74 16 38 42 17 37 93 39 52 69 59 14 24 21 96 96 43 89 100 51 95 15 38 7 55 42 28 37 49 69 75 74 36 12 16 52 1 60 43 52 80 53 65 55 73 12 50 68 100 50 18 94 16 7 100 70 1 79 58 49 47 32 74 35 95 89 38 47

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#include "./lib/debug.h"
#else
#define debug(...) 42
#endif

#define endl '\n'
#define F(type, i, s, n, step) for (type i = s; (step) > 0 ? i < (n) : i > (n); i += (step))
#define FN(type, i, s, n, step) for (type i = s; (step) > 0 ? i <= (n) : i >= (n); i += (step))
#define pb push_back
// #define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<char, int> pci;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const ll MAXM = 1e5;
int dirx[8] = {-1, 0, 0, 1, -1, -1, 1, 1};
int diry[8] = {0, 1, -1, 0, -1, 1, -1, 1};
int mod = 1e9 + 7;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double EPS = 1e-9;
double PI = acos(-1);
vl factors[MAXM + 5];

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void init()
{
    for (ll i = 1; i <= MAXM; i++)
    {
        for (ll j = i; j <= MAXM; j += i)
        {
            factors[j].pb(i);
        }
    }
}

int bin_pow(int base, int pow)
{
    int ans = 1;
    while (pow)
    {
        if (pow & 1)
        {
            ans = 1LL * ans * base % mod;
        }
        base = 1LL * base * base % mod;
        pow /= 2;
    }
    return ans;
}

int dp[105][1005];
int rec(vector<int> &v, int idx, int left_sum)
{
    int n = v.size();
    if (left_sum < 0)
        return 0;
    if (idx == n)
    {
        if (left_sum == 0)
            return 1;
        else
            return 0;
    }
    if (left_sum == 0)
    {
        return 1;
    }
    if (dp[idx][left_sum] != -1)
    {
        return dp[idx][left_sum];
    }
    return dp[idx][left_sum] = rec(v, idx + 1,left_sum) | rec(v, idx + 1, left_sum - v[idx]);
}

void solve()
{
    int n, sum;
    cin >> n >> sum;
    vi v(n);
    for (auto &e : v)
        cin >> e;
    int ans = rec(v, 0, sum);
    cout << ans;
}

signed main()

{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);

    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
#ifdef LOCAL
        std::cerr
            << "Case # " << i << endl;
        std::cout
            << "Case #" << i << endl;
#endif
        solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
    return 0;
}

~~~~~

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ENAMINE1 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ENAMINE1 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

If I understand the idea of your algorithm correctly, then no, changing the order should not change the result.

However, your code contains undefined behavior. Specifically, in the test case you have provided, the sum to try for is 5142, but the dp array has dimensions $$$105 \times 1005$$$. On the very first iteration, you set dp[0][5142] to something, and from that point onwards, the compiler is allowed to do anything. When I tried, I didn't get a different output when swapping the order, but it's very much possible that it happened with the compiler and version you used.

At least in competitive programming, I've found that some 90% of these "I changed an irrelevant thing and the result changed" comes from the code having undefined behavior.

Here's how you can diagnose issues like this by yourself next time: compile with -fsanitize=address and -fsanitize=undefined. This will make your program print errors when things like that happen. (This makes the program slower, so don't use programs compiled with these flags to measure correctness.)