PTMSSNG - Editorial

editorial
, , , , , ,
23

Just use custom hash whenever you use unordered_maps. Your AC solution with custom hash.

24

I missed this point

25 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll tc,i,n,j,x=0,y=0;
    cin>>tc;
    while(tc--){
       cin>>n;
       ll arr[4*n-1],arr1[4*n-1];
        for(i=0;i<4*n-1;i++){
            cin>>arr[i]>>arr1[i];
        }
        for(i=0;i<4*n-1;i++){
            x^=arr[i];
            y^=arr1[i];
        }
        cout<<x<<" "<<y<<endl;
        }
	return 0;
}

why it is showing WA?

26

I too was getting TLE on one testcase when I solved this problem by using unordered_map. But then, I replaced unordered_map by map and and passed all the testcases.
Can anybody tell me why I was getting TLE on single testcase ?!

27

This problem does not need an explanation>>>
You can watch this editorial.

1 Like
28

You didn’t clear value of x and y for each test case.

29

Initialise x=0 and y=0 inside while(tc–), these values are not getting updated after each test case

30

Thanks for the editorial.
May you also please show me an example of the testcase where the following code fails?
I had tried to check whether the x and y coordinates had occured only once instead of checking whether it has an odd parity.
Thanks in advance :smiley:

void solve_test_case(){
	ll n,x,y,ansx,ansy;
	cin>>n;
	vector <pair<int,int>> v1,v2;
	for(int i = 1;i <= 4 * n - 1;++i){
		cin>>x>>y;
		v1.pb(make_pair(x,y));		
	}
	sort(v1.begin(),v1.end());
	map <int,int> m1 ,m2;
	
	for(int i = 0;i < 4*n-1;++i){
		m1[v1[i].first]++;
		m2[v1[i].second]++;
		
	}
	for(auto i = m1.begin();i != m1.end();++i){
		if(i -> second == 1){
			ansx = i -> first;
		}
	}
	for(auto i = m2.begin();i != m2.end();++i){
		if(i -> second == 1){
			ansy = i -> first;
		}
	}
	cout<<ansx<<" "<<ansy<<"\n";
}
31

I was getting same then i converted first parameter of map into string coz i numbers are quiet large hence i stored into string see my soluchan.

https://www.codechef.com/viewsolution/35461177

32

Thanks for the editorial.
Can anyone please tell me why i am getting tle in one test case .
I have used map and unordered map also but still getting TLE in one test case.
Thanks in advance :grinning:
Here is the link to my solution-CodeChef: Practical coding for everyone

33

What is antihash test?

34

Hi!
Can you tell me why it works?

35

I think this will help you Blowing up unordered_map, and how to stop getting hacked on it - Codeforces

1 Like
36

Check this link-Link

1 Like
37

@sunny_52525 Hey , Since O(unordered_map)<O(map) how can we get TLE, and What is use of reserve in unordered_map??

38
39

hello ,Can you Please explain your custom hash function and how is it different from the inbuilt hash function ??

40

It saves us the time for rehashing the entire hashtable again in case when load factor threshold reaches.
refer to gfg article Sirearsh mentioned

41

Look at this

1 Like
42

So, is the hash of map stronger than unordered_map