map doesn’t uses hashing, its based on trees
@sampras123
1 Like
ok so is that the reason map require more time than unordered_map
Unordered_map is nearly 4 times faster than map. The reason why is gives TLE is it has almost O(n) collisions which can be used to build an anti hash test
i guess O(n)(How ??) collisions can removed by reserve . what is anit hash test ??
Collisions aren’t removed by reserve. It just saved us time of rehashing when size dynamically increases .
About O(n) , in case of collision it uses chaining to resolve it, hence in worse case the insertion and access takes O(n) time.
@sampras123
1 Like
Why does my previously submitted Map solution TLE out?
The same solution now is giving AC…
https://www.codechef.com/viewsolution/35446870
https://www.codechef.com/viewsolution/35617610
both codes are exactly the same. I just copy-pasted them…
I spent like 2-3 hours, skipped map went to unordered map… and came back to map… This shouldn’t have happened right?
now sue codechef xd
1 Like
in the editorial what is i.second and i. first?
I think the easiest way was to just take the xor of all x coordinates and the xor of all the y coordinates. It would easily give the answer as all other points occur even times.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ll T,N,i,ansx,ansy,x,y;
cin>>T;
while(T--)
{
cin>>N;
map<int,int> X,Y;
for(i=0;i<4*N-1;i++)
{
cin>>x>>y;
X[x]++;
Y[y]++;
}
ansx=-1;ansy=-1;
for(auto i:X)
{
if(i.second%2!=0)
ansx=i.first;
}
for(auto i:Y)
{
if(i.second%2!=0)
ansy=i.first;
}
cout<<ansx<<" "<<ansy<<"\n";
}
}
whats wrong with this it is same as the editorial but it is giving TLE in subtask 3 task#7
I didn’t get why hashing fails? What does he mean by anti hashing test cases?
Map elements are stored as a key-value pair. i.first is the key, and i.second is it’s value.
Range based for loop
std::map
std::pair
This is not entirely true.
std::map - constant O(\text{log } n) for any operation
std::unordered_map - best case O(1), and worst case O(n).
3 Likes
Video Solution:
I have swapped cin/cout with scanf/printf though I am getting TLE.
Here is link to my solution-https://www.codechef.com/viewsolution/35701669.Pls help.
Why my code is showing wrong answer? But in custom output it is working fine.
Please help me to correct it.
t=int(input())
while(t>0):
rect = int(input())
d={}
d1={}
for i in range(4*rect - 1 ):
x,y=map(int,input().split())
if(x in d.keys()):
d[x]+=1
else:
d.update({x:1})
if (y in d1.keys()):
d1[y] += 1
else:
d1.update({y: 1})
for v1,k1 in d.items():
if(v1%2!=0):
cord_x = k1
break
for v2,k2 in d1.items():
if(v2%2!=0):
cord_y = k2
break
print(cord_x,cord_y)
t-=1I tried this way using XOR operator, still, I got only subtask 1 run correctly.
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
long n;
cin>>t;
while(t--){
cin>>n;
long x[100011], y[100011];
long xp=0, xn=0;
long yp=0, yn=0;
long xz=0, yz=0;
long xpos[100011], ypos[100011], xneg[100011], yneg[100011];
for(long i=0; i<(4*n-1); i++){
cin>>x[i]>>y[i];
if(x[i]>0){
xpos[xp++]=x[i];
}else if(x[i]<0){
xneg[xn++]=x[i]*(-1);
}else if(x[i]==0){
xz++;
}
if(y[i]>0){
ypos[yp++]=y[i];
}else if(y[i]<0){
yneg[yn++]=y[i]*(-1);
}else if(y[i]==0){
yz++;
}
}
long ansx=0, ansy=0;
if(xz%2!=0){
ansx=0;
}else{
for(long i=0; i<xp; i++){
ansx= ansx^xpos[i];
}
if(ansx==0){
for(long i=0; i<xn; i++){
ansx= ansx^xneg[i];
}
ansx= ansx*(-1);
}
}
if(yz%2!=0){
ansy=0;
}else{
for(long i=0; i<yp; i++){
ansy= ansy^ypos[i];
}
if(ansy==0){
for(long i=0; i<yn; i++){
ansy= ansy^yneg[i];
}
ansy=ansy*(-1);
}
}
cout<<ansx<<" "<<ansy<<"\n";
}
return 0;
}
please help (I tried to consider negative cases too)!
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector<long long int> X, Y;
long long int T, N, i, x, y, missing_x, missing_y;
cin >> T;
while(T--){
X.clear();
Y.clear();
cin >> N;
for(i = 0; i < N*4-1; i++){
cin >> x >> y;
X.push_back(x);
Y.push_back(y);
}
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
for(i = 0; i < N*4-2; i++){
if(X[i] == X[i+1]){
i++;
}
else{
missing_x = X[i];
break;
}
}
for(i = 0; i < N*4-2; i++){
if(Y[i] == Y[i+1]){
i++;
}
else{
missing_y = Y[i];
break;
}
}
cout << missing_x << " " << missing_y << endl;
}
}
only first test case giving wrong answer
please help
Your code will fail when sol is at index 4*n-2
1 Like