wuhudsm's blog

By wuhudsm, history, 3 weeks ago, In English

In today's Codeforces Round 979, I encountered a strange situation in Problem E.

This is my submission during the contest: https://codeforces.me/contest/2030/submission/286816828. It got TLE in test #9.

However, when I modified the code as follows, it passed in about 500ms: https://codeforces.me/contest/2030/submission/286824231.

The original code:

//
dp[i&1].clear();
f[i&1].clear();
sufdp[i&1].clear();
suff[i&1].clear();
//

The modified code:

//
/*
dp[i&1].clear();
f[i&1].clear();
sufdp[i&1].clear();
suff[i&1].clear();
*/
if(i>1)
{
    for(int j=0;j<=cnt[i-2];j++)
    dp[i&1][j]=f[i&1][j]=sufdp[i&1][j]=suff[i&1][j]=0;
}
//

This is the only part I modified.

I don't understand why this code caused TLE, and I would greatly appreciate it if anyone could help.

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

Oh hi, wuhudsm.

There is a bug in GCC's implementation of std::unordered_map's clear() function. Basically, it clears the elements but not the allocated buckets. So the next consequent clear() will take time proportional to the number of buckets, which is $$$\mathcal{O}(\max n)$$$.

Cursed, I know.