DEVARRAY - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Praveen Dhinwa
Testers: Istvan Nagy
Editorialist: Praveen Dhinwa

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic maths, finding minimum and maximum of an array

PROBLEM:

You have an array of size N. Apply the following operation N - 1 times

  • Pick any two elements x, y in the array and replace them with a number z s.t. min(x, y) \leq z \leq max(x, y).

Notice that after N - 1 such operations, the array will contain a single element, as each operation reduces the size of array by 1.

You have to answer many queries - each asking whether the final single element could be equal to some given number or not.

QUICK EXPLANATION:

The final element of the array could be any number between the minimum element and the maximum element of the array, both inclusive.

EXPLANATION:

Notice that final number can not be less than the minimum element of the array.
Similarly it can not also be more than the maximum element of the array.

Lemma Any number between the minimum and the maximum element of the array, can be a possible final number.
Proof Let z be any such element, such that z lies between minimum and the maximum element of the array.
We can follow the below given strategy to always end up with z.
In the first operation, pick the minimum and the maximum element of array and replace them with z.
In the remaining N - 2 operations, we can pick z and any other element w in the array. We can always replace these two elements by z. If w < z, we can replace by max(w, z) = z, otherwise by min(w, z) = z.

So, for each query, we just have to just whether the given query element is between the minimum and maximum element in the array or not.

Note that in subtask 1, we can simply this solution even more. If array consists of all 1’s, then the final element will be 1. Similarly is the case of 2. If the array consists of both 1 and 2, then we can obtain both 1 and 2.
In other words, for each query, we just have to check whether that number is present in the array or not.

Time Complexity:

\mathcal{O}(N) to find the minimum and maximum elements of the array.
\mathcal{O}(Q) for answering the queries - \mathcal{O}(1) for each query.
Total \mathcal{O}(N + Q)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

2

Simply Sort the array in ascending order and check the below two conditions

  1. if t>=a[0]

  2. if t<=a[n-1]

If Both conditions are Fulfilled answer is Yes(Because the no. can be replaced by either with the minimum or maximum value or a value in between them) . If any one condition holds false then the answer is No .

3

@vipulmehta Sorting is unnecessary… just find min and max by declaring min>10^9 and max=0 and looping through array.

4

The complexity will increase O(n logn).

5

//here is a simple sorting method
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,q;
cin>>n>>q;
int a[n+1],i;
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
while(q–)
{
int t;
cin>>t;
if(t>=a[0] && t<=a[n-1])
cout<<“Yes”<<endl;
else
cout<<“No”<<endl;
}
return 0;
}

6

Hi. Whats wrong with my code? [python]

    x = map(int,raw_input().split())
    n,q=x[0],x[1]
    a=map(int,raw_input().split())
    while q>0:
    	v=int(raw_input())
    	if(v>=min(a) and v<=max(a)): print "Yes"
    	else: print "No"
    	q-=1
7

@singerisbest This is your corrected code.[PYTH 3.5]

n,q=map(int,input().split())
a=list(map(int,input().split()))
Min=min(a)
Max=max(a)
while q>0:
    v=int(input())
    if v>=Min and v<=Max:
        print ("Yes")
    else:
        print ("No")
    q-=1