Блог пользователя atlasworld

Why unordered_map giving wrong answer while map giving correct for the same problem.
Автор atlasworld, история, 6 лет назад, По-английски

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 ! :

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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].

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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.

        → Ответить