Hello, hope you are all well. As a fellow Codeforcer, I hate the feeling when my code gets hacked or stuck on a private test case for a trivial reason. Thus I wanted to create this thread where everyone is encouraged to share some niche case where their code unexpectedly broke :(
I'll start first:
In the Hello 2025 problem A, my unordered hash structure got TLE hacked. Solution is the use a custom hash function, courtesy of Neal's post.
In Codeforces Round 996 problem D, I tried printing a double to console in cpp. For large values, doubles defaults to scientific notation (e.g. 1.2345e+7), so I was stuck on that private test case for the whole contest :(. Solution is to cast the result to int or long long before printing.
I've read somewhere that sqrt and log functions can have precision issues at large values? I've never encountered an error when using them so far though.
I hope my mistakes are helpful to you all :)
For your second point, no need to cast it. You can just use
cout << fixed << your_double
next time.Don’t use normal polynomial hashing (even triple hashing) with small fixed modulos ($$$\approx 10^9$$$) in a round with open hacking because they are pretty easy to hack. It’s better to avoid using hashing in rounds with open hacking, but if you are forced to, make sure to randomize everything (even the alphabet).
Avoid dealing with doubles when 64-bit integers are involved.
Make sure that you don’t memset a large array of constant size in every testcase as many problem setters forget to include a test with max number of testcases in the pretests.
v.clear() doesn’t free the vector’s memory so if you are doing a small to large trick the memory complexity would still be $$$O(n \log n)$$$ which might MLE in some cases. However v.clear(); v.shrink_to_fit(); frees its memory and makes the memory complexity $$$O(n)$$$ in this case.
for last point, can't we directly use v = {}; instead of v.clear(); v.shrink_to_fit(); ?
People used to do vector().swap(v) before shrink_to_fit() was introduced into STL.
Any code snippet on how to randomize everything for hashing?
that last point is gold.
I didnt know that! Wow.
for the last one, you could also do smth like vector().swap(v); which achieves the same thing.
mine: never use unordered_map in codeforces contests
That's a bit extreme though. You just need a custom hash function most of the time
Not really... Even on random tests, unordered_map is not a lot faster than map, so just don't use it and be safe...
It's $$$O(1)$$$ vs $$$O(\log n)$$$ on average. Obviously, that difference will matter on some problems. Avoiding hashed types in all cases to "be safe" will cost you eventually
As I said, unordered_map is not a lot faster, because even it's O(1) in theory, it's constant is very very bad and doesn't give you a significant improve.
I've read somewhere that sqrt and log functions can have precision issues at large values? I've never encountered an error when using them so far though,
recently I have encountered that (sad).Recalling This
hahahaha yup
Here's one that has gotten me a few times: when you're solving a problem with $$$998244353$$$ or $$$10^9 + 7$$$ ($$$mod$$$), make sure you return your answer as
((answer % MOD) + MOD) % MOD
because if your answer went negative, the % operator will not make it positive, so you have to add the mod to get it positive.you can write a
struct modint
before contesthttps://paste.ubuntu.com/p/GTHGBz3VkJ/
So this just handles all the mod stuff for you? That seems pretty convenient, I'll try to find one, thanks.
I've faced the 1st and 3rd issues before.
1st issue: I am using Neal's custom hash for an unordered map after reading Neal's blog.
3rd issue (sqrt): I asked for help in this blog of mine after facing a problem in a contest using the sqrt function. Blog Link
Don't use "funny numbers" even in cases where you think any constant would work
If I had a bug like this in contest and someone was targeting me with a hack then they'd get me anyway, but using less common numbers can protect from other hacks after the contest