PROBLEM LINK:
Author: Alexey Zayakin
Testers: Hasan Jaddouh
Editorialist: Alexey Zayakin
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)