atlasworld's blog

Why unordered_map giving wrong answer while map giving correct for the same problem.
By atlasworld, history, 5 years ago, In English

Hello , I was solving 510D .

Here are my two submssions : link1 , link2

why map in link1 is giving correct answer while un.map gives wrong.

the question is to choose k subsets ,to make their gcd = 1 and minimise the cost of choosing .

Any idea ! :

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

std::map sorts key values, so while iterating them you go from less to bigger and that's what you need for this problem. However, unordered_map does not sort them and it leads to WA.

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

    TooNewbie but why we need order to be sorted . why we need to iterate from lesser to higher . ?

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

      You need to minimize the value of mp[1] since the possibility of traveling to that point is enough to visit all positions. While considering the values from lower to higher and if you had 1 in your map, it will appear earlier, consequently, you will find more optimal choices for mp[1].

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

        okay , i understand . basically u r saying , for a particular mp[gcd] value , we have to check all pair , if we use un.map then some values may skip which will reduce our optimallity .

        for the help.

        → Reply