adaptatron's blog

[Tutorial] : Quirks of Non Existent Map Elements
By adaptatron, 13 days ago, In English

I created a blog that talks about 3 quirks of maps/multisets.

  1. Accessing non existent elements in maps keyed on characters may lead to WA.
  2. Accessing non existent elements in maps keyed on integers may lead to TLE.
  3. Using the fancy count operator in multisets may lead to TLE.

There's no new/unique insights, I just documented my personal experience with these quirks, along with the problems link where I first encountered this issue. It might be helpful to beginners in competitive programming.

https://cfstep.com/training/tutorials/general-techniques/quirks-of-non-existent-map-elements/

  • Vote: I like it
  • -22
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it +17 Vote: I do not like it

The summary is a failure. It has nothing related with char int count, it is completely caused by other issues.

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

    Could you please elaborate? Which of the 3 section's summary are you talking about? If you're talking about the last section, note that it's not a summary, just an off-topic fact that multiset.count doesn't work in $$$O(log(n))$$$.

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

      Specific type of key doesn't lead to specific result. You can get either WA or TLE when using either char, integer or whatever your key is and the result is only dependent on context where the map is used.

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

        Agreed. In the blog, I already talk about the context, and it has no statement saying that it will lead to TLE/WA in general. The blog just describes a scenario where using maps keyed on character leads to different size than expected, a scenario where I used maps keyed on integer and got TLE and a tip regarding multiset.count.

        Well, if you're talking about the intro to the blog on Codeforces, apologies if it sounded misleading. My interpretation for "can lead to WA" was that it will not necessarily lead to WA always, further context is anyway is described in the blog. Corrected it to "may lead to WA". Sorry for my bad english.

        → Reply