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

Автор Legend_of_Azkaban, история, 4 года назад, По-английски

problem link

SOLUTION — Geeks for Geeks

I have also seen william lin solve it using hash_map in his cses speedrun video on youtube.

But C++ STL unordered_map is a 1 to 1 mapping of key and value. So say x = 12, Now we could make x by doing (a1+a4) + (a2+a3) = 5 + 7. But let's say (a3+a4) = 7 as well , and as unordered_map records only the latest occurrence of 7, so we only have 7 at (a3+a4). As a4 is repeating in both (a1+a4) and (a3+a4), these are not distinct positions and we don't have an answer.

This is not a perfect example, because we can discover other good ways to make 12 if we check other possible combinations. And also a perfect example might not exist given that this is a well-known solution, I just wanted to convey my idea why unordered_map might fail and it is not all clear to me why it actually works for every possibility.

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

»
4 года назад, # |
Rev. 13   Проголосовать: нравится +8 Проголосовать: не нравится

I believe the intuition is exactly that. Map stores the rightmost occurence and you iterate pairs left to right

Let's assume that four numbers that we seek are located in the array as

A.......B.......C......D

Obviously hashmap is going to store (C+D) and the first pair you discover in the second nested loop is (A+B)

The problem with your example is that we don't actually care about a1 + a4 if a1 + a2 + a3 + a4 == 12. Yes, this pair maybe fruitless, but we're not even going to reach it. We will first encounter a1 + a2 and retrieve a3 + a4 from the hashmap.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the help. The one fact that we are always going to find $$$(A,B)$$$ first and retrieve $$$(C,D)$$$ covers it. If $$$(C,D)$$$ collides with $$$(A,B)$$$, it never was an answer in the first place. And if there are other pairs colliding with $$$(A,B)$$$ but equal to $$$C+D$$$, they are going to be replaced by $$$(C,D)$$$ in the unordered_map anyway as $$$(C,D)$$$ occurs late.