2

I was doing this problem for practice. Here is my initial solution:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, x;
  cin >> n >> x;

  unordered_map<ll, int> cnt;
  ll sum = 0;
  ll res = 0;
  cnt[0] = 1;

  while(n --) {
    int a;
    cin >> a;
    sum += a;
    res += cnt[sum - x];
    cnt[sum] ++;
  }

  cout << res;
}

The solution is pretty simple, using a prefix sum and for each element check how many times the complement number occurred before. Here, I use unordered_map in order to count the frequency of each element, as a regular bitmap would be far too large. However, when submitting this I got time limit exceeded on a few test cases. I was stumped for a long time, so I had to look at the solution. The solution was very similar to mine, but there was a difference in that they used map while I use unordered_map. So I changed which map I used, and when submitting again it got accepted. I am curious as to why using a map is faster than unordered_map in this situation, as I thought map was slower due to it's nature of sorting all elements coming in.

Higigig
  • 1,175
  • 1
  • 13
  • 25
  • I am curious, how does `std::unordered map` perform if provided a third template argument for a custom hash object. Perhaps an identity hash is faster than their `std::hash` implementation. – Camwin Apr 07 '22 at 02:39
  • 2
    What happens if `x > sum` in `res += cnt[sum - x];`? Don't leave spaces in `n --` or `cnt[sum] ++`. Yes, whitespace is ignored, but readability suffers. See Also, [Why should I not #include ?](https://stackoverflow.com/q/31816095/3422102) – David C. Rankin Apr 07 '22 at 02:50
  • You will have to look into the implementations of both. That being said maintaining a sorted list isn’t slow if you do it right and it can speed up access. – Taekahn Apr 07 '22 at 02:55
  • You are not just looking up in a map, you are also building the map inside that loop. If an item doesn't exist, `[]` inserts a new item -- that insertion time is probably what you are experiencing. Building an unordered_map may take more time than building a `std::map`. Pure lookups *after* the map is built, that is where `std::unordered_map` will be superior to `std::map`. – PaulMcKenzie Apr 07 '22 at 04:06
  • 1
    @PaulMcKenzie in general I agree, but it’s worth noting the worst case lookup is worse. N vs log n. For all we know the test cases could be heavily triggering the worst case scenario. Just goes to show that “best” is always subject to your specific use case. – Taekahn Apr 07 '22 at 04:43
  • 1
    Do not use `#include `. It does not follow the standard and clogs your namespace. – Sebastian Apr 07 '22 at 06:49

0 Answers0