Same Code give different output

Hello There,
I was solving the CSES problem Sum of Two Values. it is the same as like leet code problem named Two Sum.

I code it that way, buuuuut.
I got TLE. Then I checked USACO and then I copy pasted the code given on the website and it worked. although they are the same.

My code:

#include <bits/stdc++.h>
typedef long long ll;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define f(i, a, b) for (int i = a; i < b; i++)
#define vi vector<int>
#define vl vector<ll>
#define vc vector<char>
#define vs vector<string>
#define inp cin >>
#define out cout <<
#define mii map<int, int>
#define mll map<ll, ll>
#define mci map<char, int>
#define mcc map<char, char>
#define pll pair<ll,ll>
#define uset unordered_set<ll>
#define sset set<ll>
const ll N = 2e5+10;
using namespace std;
int main(){
    fast_cin();
    ll n,x;
    cin >> n >> x;
    vector<int> v(n);

    unordered_map<int,int> map;

    for(int i=0;i<n;i++){
        cin >> v[i];
    }
    for(int i=0;i<n;i++){
        int get = x - v[i];
        if(map.count(get)){
            cout << i+1 << " " << map[get]+1 << endl;
            return 0;
        }
        map[v[i]] = i;
    }
    cout << "IMPOSSIBLE" << endl;

}

USACO code:

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, x;
	cin >> n >> x;

	vector<int> values(n);
	for (int i = 0; i < n; i++) { cin >> values[i]; }

	// use a map to avoid using a very large array
	map<int, int> val_to_ind;
	for (int i = 0; i < n; i++) {
		// target minus a number is the other number
		if (val_to_ind.count(x - values[i])) {
			cout << i + 1 << " " << val_to_ind[x - values[i]] << endl;
			return 0;
		}
		val_to_ind[values[i]] = i + 1;
	}

	cout << "IMPOSSIBLE" << endl;
}

Can Someone Explain me, What the heck in happening here?

1 Like

tl;dr use map instead of unordered_map: (Optional) Hashmaps

Hey, Thanks for your response
can you elaborate a little bit more?
I tried to read from your given link but I guess it is a little confusing to me.
Can please you explain in simple terms?
Thanks

Can you elaborate on which part you find confusing?

As per the code I’ve shared above,
Why unordered_map is giving TLE and a map not?
Wouldn’t the Time Complexity be the same for both codes?
And the gp_hash_table which is mentioned in your link, will that optimize the Time complexity or it will reduce the iteration in the code?

These questions might sounds stupid, but I’m newbie in CP, but i want to get into it. so can you help me?

Thanks

The link I shared contains code that generates a test case where unordered map takes \Theta(N^2) time on this CSES problem, which obviously results in TLE. On the other hand, map is guaranteed to take O(N\log N) time.

If you use an appropriate randomized hash function (as described in the link), then both unordered_map and gp_hash_table will take O(N) time with high probability on any test case. gp_hash_table usually has a smaller constant factor than unordered_map.