alfaloo's blog

By alfaloo, history, 5 weeks 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
  • +21
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +13 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.

»
5 weeks ago, # |
  Vote: I like it +22 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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      People used to do vector().swap(v) before shrink_to_fit() was introduced into STL.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any code snippet on how to randomize everything for hashing?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    that last point is gold.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for the last one, you could also do smth like vector().swap(v); which achieves the same thing.

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

mine: never use unordered_map in codeforces contests

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Not really... Even on random tests, unordered_map is not a lot faster than map, so just don't use it and be safe...

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          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.

»
5 weeks 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).

»
5 weeks ago, # |
  Vote: I like it 0 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.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't use "funny numbers" even in cases where you think any constant would work

Spoiler for "Nene vs. Monsters" problem

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