Hello Codeforcers! I need your help to debug this strange TLE verdict. I was trying to implement the editorial of the problem D. Chip Moves. My implementation which is very similar to the editorial is this:
using ll = long long;
#define rep(i, n) for (ll i=0; i<n; ++i)
#define rep1(i, n) for (ll i=1; i<=n; ++i)
const ll MAXN = 2e5 + 5;
ll A[MAXN][4];
void solve() {
constexpr ll mod = 998244353;
memset(A, 0, sizeof A);
ll n; cin >> n;
ll k; cin >> k;
ll tot = 0;
ll step = k;
ll CUR = 0;
ll DP = 1;
ll SAME = 2;
ll ANS = 3;
A[0][DP] = 1;
ll iters = 0;
while ((tot += step) <= n) {
iters++;
rep (i, n+1) A[i][CUR] = 0;
rep (i, step) A[i][SAME] = 0;
for (ll i = max<ll>(step-4, 0); i <= n; ++i) {
(A[i][CUR] += A[i % step][SAME]) %= mod;
// This line seems to cause the TLE
(A[i][ANS] += A[i][CUR]) %= mod;
(A[i % step][SAME] += A[i][DP]) %= mod;
}
swap(CUR, DP);
step++;
}
for (ll i = 1; i <= n; ++i) {
cout << A[i][ANS] << " ";
}
cout << endl;
// cerr << "iters: " << iters << endl;
}
which received a TLE verdict. Upon testing this locally, it seems to work pretty fast uptill n = 170000, but when putting n = 180000, the program suddenly stops running and hangs. Upon further investigation inside the solve function, this one line (A[i][ANS] += A[i][CUR]) %= mod; seems to be the issue! Just uncommenting this one line gives the solution extremely fast (although obviously wrong)! However uncommenting this line out causes the program to TLE.
What is about this one small line which is a simple O(1) operation which causes the whole program to simply hang? I've been stuck on this weird bug for a while and would like to seek your help.








Auto comment: topic has been updated by avyjit (previous revision, new revision, compare).
Auto comment: topic has been updated by avyjit (previous revision, new revision, compare).
Remove or comment out this unused code:
Nope, I removed the unused code and the same bug persists.
i think its something to do with your template or some optimizers or try with ll int since ur using 2 dimensional array or dp
I think if you change the code to this, it should be accepted
Avoid using to much long long, int have a better time complexity when deal with operation
i believe it's less avoiding long long but more avoiding overusing mod operations, as they are slow.
And maybe your template is affecting it too!
This is your code (Accepted) if remove the unused code: https://mirror.codeforces.com/contest/1716/submission/309865290 (Shout out to ComRSMaster)
I just realized that your code: https://mirror.codeforces.com/contest/1716/submission/309780027 got AC when I submitted it again.
However, the above code gives WA on test 4.