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.
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 consequentclear()
will take time proportional to the number of buckets, which is $$$\mathcal{O}(\max n)$$$.Cursed, I know.
; )