 # PHBCLS - Editorial

Practice

Author: Sakchi Agarwal
Tester: Sparsh Kedia
Editorialist: Ayush Shukla

SIMPLE

Sorting

# PROBLEM:

Given intervals of equal length , you have to find if any interval overlap with the other.

# QUICK EXPLANATION:

A person will not overlap with any person if it do not overlaps with the persons who are standing before and after him in the line. If this is true for every person then there is now overlapping and the exercise is Perfect .

# EXPLANATION:

If we have N persons standing , we have to find the order in which they are standing. So we will sort the positions. Now for each i_{th} person we will check if it overlaps with {(i-1)}_{th} person where (2 \leq i \leq N) .
If two persons with hand length K are standing at position X_1 and X_2 , (X_1 \leq X_2) then they will overlap if (X_1+k > X_2 - k). If no person is overlapping with the next one then the exercise will be Perfect else Imperfect

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
ll a[n];
for(ll i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
ll f=1;
for(ll i=1;i<n;i++){
if(a[i]-k<a[i-1]+k){
cout<<"Imperfect\n";
f=0;
break;
}
}
if(f)cout<<"Perfect\n";
}
}

Tester's Solution
import math
t = int(input())
while t>0 :
n,k = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
l.sort()
f = 1
for i in range(1,n):
if((l[i]-k) < (l[i-1]+k)):
print("Imperfect")
f=0
break

if(f==1):
print("Perfect")

t = t-1


Feel free to share your approach.
Happy Coding!

1 Like