Extremely strange slowdown in C++

Revision en7, by avyjit, 2025-03-10 19:04:06

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.

Full code

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.

Tags debugging, c++, tle, optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English avyjit 2025-03-10 19:04:33 0 (published)
en7 English avyjit 2025-03-10 19:04:06 4371 (saved to drafts)
en6 English avyjit 2025-03-10 19:00:25 0 (published)
en5 English avyjit 2025-03-10 18:59:11 49 Tiny change: ' ' -> ' // This line seems to cause the TLE\n '
en4 English avyjit 2025-03-10 18:58:31 12
en3 English avyjit 2025-03-10 18:57:27 4 Tiny change: 'is: \n```c++\nusing ll' -> 'is: \n```cpp\nusing ll'
en2 English avyjit 2025-03-10 18:56:58 19
en1 English avyjit 2025-03-10 18:55:49 1973 Initial revision (saved to drafts)