PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Soumyadeep Pal
Tester: Tejas Pandey and Utkarsh Gupta
Editorialist: Taranpreet Singh
DIFFICULTY
Simple
PREREQUISITES
None
PROBLEM
Given an array A containing N integers and a constant integer K, you are allowed to perform the following operation on A.
- Choose two distinct indices i and j such that A_i + A_j \leq K, and remove either A_i or A_j from A
Determine if we can obtain an array containing only one element using the above operation.
QUICK EXPLANATION
- It is possible only when the sum of minimum and maximum element of A does not exceed K.
- If the above condition is true, we can select indices of minimum and maximum of the current array, and delete maximum at each step.
EXPLANATION
Observation 1: It is optimal to choose index of minimum element in each operation
Proof: Assume we choose indices i and j for current operation, and the index of minimum element is k. WLOG assume A_k \leq A_i \leq A_j. Since we have A_i + A_j \leq K, we also have A_k \leq A_i, so A_k+A_j \leq A_i+A_j \leq K. We can see that by choosing pair (k, j), we are still able to perform the operation.
Now, we know that one of the chosen elements in each operation shall be the minimum of the given array. Let’s call it min.
The largest element x which can be removed from array must satisfy x + min \leq K, which means x \leq K-min.
So if the array contains an element y \gt K-min, it is impossible to include y in any operation. So there would be at least 2 elements left at the end.
Hence, if the sum of minimum and maximum elements exceed K, then it is not possible to obtain an array containing only one element.
If you wish to generate the actual operations
Observation 2: It is optimal to delete the larger element at each operation.
**Proof: ** Let’s assume we delete the minimum at some operation. Then for the next operation, the minimum chosen would be larger, possibly restricting us to including the maximum element.
For example, consider A = [2,4,6,7] and K = 9. If we choose pair (2, 7) and delete 2, we can no longer remove any element from [4,6,7].
TIME COMPLEXITY
The time complexity is O(N) or O(N*log(N)) per test case.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, k; cin >> n >> k;
int mx = 0, mn = 1e9;
for (int i = 0; i < n; i++) {
int x; cin >> x;
mn = min(mn, x);
mx = max(mx, x);
}
cout << ((n == 1 || mx + mn <= k) ? "YES" : "NO") << '\n';
}
signed main() {
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
Tester's Solution 1
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1000;
const int MAX_N = 100000;
const int MAX_K = 1000000000;
const int MAX_A = 1000000000;
const int MAX_SUM_LEN = 500000;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define ll long long
const ll LIM = 1000000000;
#define pll pair<ll ,ll>
#define tll tuple<ll, ll, ll>
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
void solve() {
int n, k;
n = readIntSp(1, MAX_N);
k = readIntLn(1, MAX_K);
sum_len += n;
assert(sum_len <= MAX_SUM_LEN);
int a[n];
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(1, MAX_A);
a[n - 1] = readIntLn(1, MAX_A);
sort(a, a + n);
if(n == 1 || a[n - 1] + a[0] <= k) cout << "YES\n";
else cout << "NO\n";
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.txt", "r" , stdin);
freopen("outputf.txt", "w" , stdout);
#endif
fast;
int t = 1;
t = readIntLn(1, MAX_T);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_len << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
//cerr<<"Answered yes : " << yess << '\n';
//cerr<<"Answered no : " << nos << '\n';
}
Tester's Solution 2
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1000;
const int MAX_N = 100000;
const int MAX_SUM_LEN = 500000;
const int MAX_Ai = 1000000000;
const int MAX_K = 1000000000;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
void solve()
{
int n=readInt(1,MAX_N,' ');
int k=readInt(1,MAX_Ai,'\n');
vector <int> v;
for(int i=1;i<=n;i++)
{
int c;
if(i!=n)
c=readInt(1,MAX_Ai,' ');
else
c=readInt(1,MAX_Ai,'\n');
v.push_back(c);
}
if(n==1)
{
cout<<"YES\n";
return;
}
sort(v.begin(),v.end());
if((v[0]+v[n-1])<=k)
cout<<"YES\n";
else
cout<<"NO\n";
}
signed main()
{
fast;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t = readInt(1,MAX_T,'\n');
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class REMELEM{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), K = ni();
int[] A = new int[N];
for(int i = 0; i< N; i++)A[i] = ni();
Arrays.sort(A);
if(N == 1 || A[0]+A[N-1] <= K)pn("YES");
else pn("NO");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new REMELEM().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
