avyjit's blog

By avyjit, history, 7 hours ago, In English

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.

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

»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by avyjit (previous revision, new revision, compare).

»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by avyjit (previous revision, new revision, compare).

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Remove or comment out this unused code:

#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;

template <typename K, typename V>
using umap = gp_hash_table<K, V, custom_hash>;

template <typename T>
using uset = umap<T, null_type>;

template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;