PTMSSNG - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Áron Noszály
Tester: Encho Misev
Editorialist: Áron Noszály

DIFFICULTY:

SIMPLE

PREREQUISITES:

Observations, Data structures, Sorting, Bitwise operations

PROBLEM:

There are 4N-1 different points in the plane. You should find a point P such that together they form N axis-aligned non-degenerate rectangles. It is guaranteed that the answer exists and is unique.

QUICK EXPLANATION:

Let’s consider all 4N points, the number of points with a given x or y coordinate is always even. By taking away exactly one point, one vertical count and one horizontal count will be odd, those will be the coordinates of the point that we are searching

EXPLANATION:

One possible approach is to start with small cases, let N=1 draw a rectangle and take one of its vertices away, we can instantly recover the missing point P (even if we have a really short memory :D), because no matter what, there’s only one point on both the vertical line and horizontal line through P, and in the other vertical/horizontal lines there are 0 or 2 points.

It might immediately be clear that parity is the key, by extending the idea and adding a few more rectangles we can see that each extra rectangle contributes either 2 or 0 points to each vertical/horizontal line. Therefore the lines containing the missing point will surely have an odd amount of points and the rest of lines will have an even amount of points, so it’s enough to find these two lines and at their intersection will be P. Mathematicians call this an invariant, we can simply say that the parity of the number of points in some vertical/horizontal is invariant to adding more rectangles.

There are multiple ways to implement the above idea:

  • A simple bruteforce algorithm for checking every possible horizontal and vertical line, the complexity is O(N^2) which is enough for the first subtask.
  • We can use a data structure like std::map in C++, TreeMap in Java or a dictionary in Python to maintain the number of points in each horizontal and vertical line.
  • Sort all the x and y coordinates and loop through them to find the one with odd frequency.

We could think that simply changing the data structure to a hash-based one with O(1) queries/updates (like unordered_map in C++ or HashMap in Java) should work, yes it may do trick and our complexity would be O(N), however I was evil and included some antihash tests.

There is a much better way! Note that taking the bitwise xor of the x coordinates of all 4N-1 points will actually just give us P's x coordinate, since each of the other x coordinates is present an even number of times they cancel out, while P's x coordinate is in the input an odd number of times. Similarly for the y coordinate. So now we have an algorithm with O(N) time complexity.

SOLUTIONS:

Setter's Solution
Sorting method
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin>>T;
	while(T--) {
		int n;
		cin>>n;
		vector<int> x, y;
		for(int i=0;i<4*n-1;++i) {
			int X,Y;
			cin>>X>>Y;
			x.push_back(X);
			y.push_back(Y);
		}
		sort(x.begin(),x.end());
		sort(y.begin(),y.end());
		int ans_x=-1,ans_y=-1;
		auto find_odd=[&](vector<int>& x) -> int {
			int i,j;
			for(i=0;i<(int)x.size();i=j) {
				j=i;
				while(j<(int)x.size() && x[i]==x[j]) {
					j++;
				}	
				
				if((j-i)&1) return x[i];
			}
			return -1;
		};
		
		ans_x=find_odd(x);
		ans_y=find_odd(y);
		cout<<ans_x<<" "<<ans_y<<"\n";
	}
	return 0;
}
Using map
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int T;
	cin>>T;
	while(T--) {
		int n;
		cin>>n;
		map<int,int> X,Y;
		for(int i=0;i<4*n-1;++i) {
			int x,y;
			cin>>x>>y;
			X[x]++;
			Y[y]++;
		}
		
		int ans_x=-1, ans_y=-1;
		for(auto i:X) {
			if(i.second&1) ans_x=i.first;
		}
		
		for(auto i:Y) {
			if(i.second&1) ans_y=i.first;
		}
		
		assert(ans_x!=-1 && ans_y!=-1);
		cout<<ans_x<<" "<<ans_y<<"\n";
	}
}
XOR solution
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T;
	cin>>T;
	while(T--) {
		int n;
		cin>>n;
		int ans_x=0, ans_y=0;
		for(int i=0;i<4*n-1;++i) {
		    int x,y;
		    cin>>x>>y;
		    ans_x^=x;
		    ans_y^=y;
		}
		cout<<ans_x<<" "<<ans_y<<"\n";
	}
	return 0;
}
Tester's Solution
#include <iostream>
#include <stdio.h>
#include <map>
using namespace std;

int t;
int n;
map<int, int> rows, cols;

int main()
{
    int i,j;
    int test;

    scanf("%d", &t);

    for (test=1;test<=t;test++)
    {
        rows.clear();
        cols.clear();

        scanf("%d", &n);

        for (i=1;i<=4*n-1;i++)
        {
            int x, y;

            scanf("%d %d", &x, &y);

            auto it = rows.find(x);

            if (it != rows.end())
            {
                (*it).second++;
            }
            else
            {
                rows.insert(make_pair(x, 1));
            }

            it = cols.find(y);

            if (it != cols.end())
            {
                (*it).second++;
            }
            else
            {
                cols.insert(make_pair(y, 1));
            }
        }

        int r, c;
        for (auto it = rows.begin(); it != rows.end(); it++)
        {
            if ( (*it).second % 2 == 1 )
                r = (*it).first;
        }

        for (auto it = cols.begin(); it != cols.end(); it++)
        {
            if ( (*it).second % 2 == 1 )
                c = (*it).first;
        }

        printf("%d %d\n", r, c);
    }

    return 0;
}
14 Likes

How did you just defined a whole function in main???

Or we could make use of the fact that the rectangles are always going to be axis - parallel . So every x and y coordinate will come twice. Now the problem simply reduces to doing xor of x and y coordinates .

6 Likes

that is lambda function.

1 Like

Quick and easy explanatory video : Missing a Point | Code Chef July Long Challenge 2020 - YouTube

1 Like

i was getting TLE when i solved it by using unordered map. i just counted the frequency of each number and the number whose frequency was odd was my answer. its time complexity was O(n). Can somebody tell me why i was getting TLE
Thanks is advance
here is the link to my solution- CodeChef: Practical coding for everyone

3 Likes

I too was getting TLE on some cases as i thought the limit was too tight, so I swapped cin/cout with scanf/printf and passed the tcs :slight_smile:

1 Like

My first video solution for a codechef problem PTMSSNG!

Hope you guys like it!

2 Likes

Also i tried it to solve by other method but i was getting TLE in that too.
here too i used unordered_map.The task was to find the coordinates that were occuring odd number of times. Here,i have created two variables s1 and s2 used for keeping track of coordinates that are missing of a rectangle. let x and y be input coordinates of rectangle. We add x and y to s1 and s2 respectively if the frequency of x and y is 0 else subtract the number from s1 and s2 along with changing its frequency to 0.
At last, the values remaining in s1 and s2 will be our required answer.
Can somebody tell me why i was getting TLE in this too.
thanks in advance
here is the link to my solution-CodeChef: Practical coding for everyone

The limits weren’t too tight as it’s working fine for sorting method mentioned in the setter’s solutions where the time complexity was nlogn.

It’s called a lamba. We can define those in main (or any function). Lamba’s can also be used as custom comparators for std::sort (or set or priority_queue, or basically any STL that allows a comparator).

2 Likes

hello
what do you mean by antihash tests?

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

int main() {
	int t;
	cin >> t;
	while(t--){
	    int n;
	    cin >> n;
	    int pX = 0,pY = 0;
	    for(int i=1;i<4*n;i++){
	        int x,y;
	        cin >> x >> y;
	        pX^=x;
	        pY^=y;
	    }
	    cout << pX << ' ' << pY << '\n';
	}
}
1 Like
2 Likes

fixed few things, and now it gives AC
https://www.codechef.com/submit/complete/35605482

remember .find() is always faster in maps then direct reads,

1 Like

I used an unordered map and I got TLE. I used just map and I got AC!

Following is my attempt to explain this using sets,

use reserve for unordered map

It was the game of odd and even so simply use xor.
every x and y coordinate should occur even number of times.

     test{
    ll n,x,y,ans1=0,ans2=0;cin>>n;
    for(int i=0;i<4*n-1;++i){
        cin>>x>>y;
        ans1^=x;
        ans2^=y;
    }
    cout<<ans1<<" "<<ans2<<endl;
    
}
4 Likes

@aadarsh_1013 Use std::map instead. Go through this link

1 Like