alfaloo's blog

Common hacks / tricks we can learn from
By alfaloo, history, 14 hours ago, In English

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 :)

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

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

For your second point, no need to cast it. You can just use cout << fixed << your_double next time.

→ Reply
»
11 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

  • 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.

→ Reply
  • »
    »
    6 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    for last point, can't we directly use v = {}; instead of v.clear(); v.shrink_to_fit(); ?

    → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any code snippet on how to randomize everything for hashing?

    → Reply
»
9 hours ago, # |
  Vote: I like it +9 Vote: I do not like it

mine: never use unordered_map in codeforces contests

→ Reply
  • »
    »
    29 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's a bit extreme though. You just need a custom hash function most of the time

    → Reply
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply
»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply