PHBCLS - Editorial

PROBLEM LINK:

Practice

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

DIFFICULTY:

SIMPLE

PREREQUISITES:

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