Vatsal38's blog

TLE In 1234B2 social networking
By Vatsal38, history, 5 years ago, In English

solution link: https://ideone.com/Dn2nQN problem link : https://mirror.codeforces.com/problemset/problem/1234/B2 Why it is giving tle at 23rd case?

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

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

Most likely it is because you are using an unordered map. Some tests are made specifically to mess with that container. Try using a map instead.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah it worked thanks ! but why was it not working with unordered map. they are faster right?

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

      Unordered maps are faster? Can you tell me why this is so in the first place?

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

        In map data is stored in sorted order while in unordered map it is not. operations like insert delete takes log n in map while o(1) in unordered

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

          Are you sure operations in Unordered Map takes O(1)?

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

            i am just a beginner. i have studied o(1) for unordered map in general. can you please tell me why map wprking instead of ump

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

          Read this: https://en.m.wikipedia.org/wiki/Hash_table

          And share this with every programmer who programs without reading the manual.

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

            In average case its O(1) atleast read what you are sending

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

              On average != Worst case. Read again.

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

                yup but most of the times its O(1). i think this test case was made to avoid ump as lot of collisions is happening but still using ump is better than map right?

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

                  yup but most of the times its O(1). i think this test case was made to avoid ump as lot of collisions is happening

                  You just contradicted yourself and answered your original question yourself.

                  using ump is better than map right?

                  You cannot generalize stuff this way. One obvious example, how do you get the minimum/maximum element in the hash table efficiently?

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

                  ok i got your point thanks

                  → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want more information on unordered_map and how to make it faster: https://mirror.codeforces.com/blog/entry/62393

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unordered map can have a high complexity when it is used a lot of times.

→ Reply