Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

YF_YUSUF's blog

A huge number of hacks on problem 1042C
By YF_YUSUF, 15 months ago, translation, In English

A few hours ago, the hacking phase for the round (Div. 3) ended and the system testing began. I wanted to check how many solutions failed the system tests, and I saw a huge number of TLEs on problem C. After looking at several solutions, I realized that they all had one thing in common — unordered_map.
I think many people know that unordered_map (hereafter UM) can work in both $$$O(1)$$$ and $$$O(n)$$$ time. Because of this, some people found a test case where UM runs in $$$O(n)$$$, which makes the overall complexity $$$O(n^2)$$$.
It got me wondering why people massively use UM when a regular map passes within the time limits. I asked ChatGPT to solve this problem, and it gave me a solution using UM.

ChatGPT's code

On the one hand, it’s kind of funny that people who copied from ChatGPT (or another LLM) got their solutions rejected.
On the other hand, there are people who wrote the code themselves but decided to use UM instead of map (although I think that’s their own fault because they could have just used a regular map).

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

Comments Comments (16)
| Write comment?
»
15 months ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

This is hilarious and a good entertainment too. That is, to go to the status page, pick problem C and check the TLE submissions only to see, that contestants with such submissions follow... a certain pattern, you know.

→ Reply
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Honestly I was scared with a normal map, looking at the time it took during contest and seriously considered resubmitting, thank god i didn't

→ Reply
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I believe this will pass if you sort the array before hand

→ Reply
»
15 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I am a beginner so I don't if I have a place to speak here lulw but I use unordered_map like all the time whenever I have to use something sort of a hashmap. why is it preferred to use a normal map over unordered_map? does the sorting provide some sort of a powerup?

→ Reply
  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    The reason map is preferred over unordered_map is because, when you use umap[x], it uses the hash function (default: std::hash) and some other stuff to check if umap[x] exists and returns the value if so. But if there's a hash collision (two keys in umap, say x and y) it takes up to $$$O(n)$$$ to resovle the collision and get the corresponding value. Carefully selected keys can result in a time complexity as high as $$$O(n^{2})$$$.

    → Reply
    • »
      »
      »
      15 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Ah ok, so ordered_map doesn't have this problem then? if that's so, shouldn't the normal ordered_map be used in every situation?

      → Reply
      • »
        »
        »
        »
        15 months ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        std::map takes $$$O(\log n)$$$ operations where $$$n$$$ is the number of elements in the map.

        The reason people (and ChatGPT) use std::unordered_map does $$$O(1)$$$ operations, and so is generally faster than std::map, except when hash collisions happen. Some people also don't know about the hash collisions part and don't use a custom, stronger hash which lead to hash collisions with GCC's default std::hash and std::unordered_map.

        Read this blog on std::unordered_map for preventing most hash collisions. Basically, if you use

        struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

        and unordered_map<int, int, custom_hash>, hash collisions will become much less likely.

        → Reply
»
15 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

No human would ever use unordered_map.reserve in a contest

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

    Why not? If I'm using unordered_map, it means I'm already concerned about performance, and reserve might speed up the code significantly and has no downsides, so practically no reason (at least I'm not aware of any) not to use it

    → Reply
  • »
    »
    15 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Why not? It prevents rebuilding hash map as it grows. Thus, some contestants may think that executing the reserve method may improve the performance

    → Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Why do you think so? That method doesn't seem to be something unusual. With approximate understanding on how UM works and what does unordered_map.reserve do the UM can become a powerful enough tool.

    → Reply