### qmaruf's blog

By qmaruf, history, 6 years ago,

The following code generates different result for input "54 60 16" for this problem https://codeforces.cc/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?

• 0

 » 6 years ago, # | ← Rev. 2 →   0 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, # ^ |   +3 sizeof(mem) will return exactly size of array, same as you wrote. Don't confuse that with taking sizeof pointer, which is typically a mistake.
•  » » » 6 years ago, # ^ |   0 i read it here and here
•  » » » » 6 years ago, # ^ |   0 I don't say it's incorrect, I'm just pointing out to another possbility.
 » 6 years ago, # |   +3 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.
•  » » 6 years ago, # ^ |   0 Thanks :) AC. Learnt something new.
 » 7 weeks ago, # |   0 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.