PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Tarun M
Tester: Tejas Pandey, Abhinav Sharma
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Cakewalk
PREREQUISITES:
PROBLEM:
Sneil is given N points on a coordinate graph. From these points (X_i, Y_i) he can draw horizontal and vertical lines. If he finds the number of lines that can be drawn he will get to eat Sneilium.
Since Sneil is too slow he asks you to help him with this task.
EXPLANATION:
After we have drawn all the lines, we have a grid with some lines parallel to the X axis and some lines parallel to the Y axis. The total number of lines is just the sum of the lines parallel to the X axis and the lines parallel to the Y axis.
The only catch is to handle duplicates. For that, we can use set data structure. We club all the X coordinates and all the Y coordinates into separate sets.
Finally, the total number of lines is just the sum of the sizes of both these sets.
TIME COMPLEXITY:
Ordered sets have a complexity of O(logN) per insertion. This leads to a time complexity of O(NlogN) per testcase. We can use unordered sets to reduce this to O(N) per test case.
SOLUTION:
Setter's Solution
// Author -- tarun__m
#include <bits/stdc++.h>
// Data Types
#define ll long long int
#define ull unsigned long long int
#define vll vector<ll>
#define vull vector<ull>
// I/O
#define inp(n) cin >> n
#define out(n) cout << n
#define outspa(n) cout << n << " "
#define outlin(n) cout << n << "\n"
#define spa() cout << " "
#define lin() cout << "\n"
// Funcs
#define fo(iter, start, stop) for(ll iter = start; iter < stop; iter++)
#define fos(iter, start, stop, step) for(ll iter = start; iter < stop; iter+=step)
#define all(a) (a).begin(), (a).end()
#define pb push_back
template <typename T>
T power(T a, T b) {
T ans = 1;
fo(i, 0, b){
ans *= a;
}
return ans;
}
using namespace std;
void solve(){
ll n;
inp(n);
set<ull> x_val, y_val;
fo(i, 0, n){
ull x, y;
inp(x);
inp(y);
x_val.insert(x);
y_val.insert(y);
}
outlin(x_val.size() + y_val.size());
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t, i;
inp(t);
fo(i, 0, t){
solve();
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
unordered_set<int> xx, yy;
for(int i = 0; i<n; i++){
int x, y;
cin>>x>>y;
xx.insert(y);
yy.insert(x);
}
cout<<xx.size() + yy.size()<<endl;
}
return 0;
}