qmaruf's blog

By qmaruf, history, 8 years ago, In English

The following code generates different result for input "54 60 16" for this problem http://codeforces.com/contest/431/problem/C

PC output: 931055544

Online judge output: 811386435

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll MOD = 1000000007;
ll n, k, d;
ll mem[101][2];

ll solve(ll cursum, int exist)
    if(mem[cursum][exist]!=-1)return mem[cursum][exist];
    if(cursum == n)return (ll)exist;
    if(cursum > n)return 0L;
    ll ans = 0L;
    for(ll b = 1; b <= min(k, n); b++)
        ans = (ans + solve(cursum + b, exist|(b>=d)))%MOD;
    mem[cursum][exist] = ans;
    return ans;
int main()
        memset(mem, -1, sizeof(mem));
        ll res = solve(0, 0);
    return 0;

Am I missing anything?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

may be because of memset memset for 2-d array should be like this memset(mem, -1, sizeof(mem[0][0])*101*2);

8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your program contains undefined behavior: it's possible that you access memory out of the mem array. If cursum > n, your function will return, but first it will read value from mem[cursum][exist], which is undefined behavior if cursum > 100.

Single undefined behavior of any kind makes your program's behavior undefined as well. Reasoning: compilers can do really cool (or weird) optimizations assuming that there is no undefined behavior. And when it happens, anything can happen and you cannot simply predict what exactly.

18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Same problem for this submission: 137826674. I get correct output on my computer (NO YES NO NO YES YES), but on online judge it's all just YES.