qmaruf's blog

By qmaruf, history, 6 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()
{
    while(cin>>n>>k>>d)
    {
        memset(mem, -1, sizeof(mem));
        ll res = solve(0, 0);
        cout<<res<<endl;
    }
    return 0;
}

Am I missing anything?

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

»
6 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);

»
6 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.

»
2 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.