PROBLEM LINK:
Author: Abizer Lokhandwala
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov
DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
Chef searched a given number (rating) in a given sorted array (in ascending order) through a sequence of queries of the form “which number is at position i?”. The answers to these queries are given, the indices are unknown. Determine whether some queries in the sequence are redundant (from previous queries and monotonicity of the array it is clear that given number cannot be located at the position of the query).
QUICK EXPLANATION:
Process the ratings one-by-one, maintain range of possible values of Reziba’s rating (initially [-\infty, +\infty], where). If the current rating does not belong to the range, the sequence is redundant and the answer is NO. Depending on whether the rating is higher or lower than Reziba’s, change the corresponding bound of the range.
EXPLANATION:
When can we conclude that the sequence has mistakes? In problem statement, there is only one constraint:
However, Chef will never go beyond a person whose rating Chef has asked before. For example, if Chef was walking to the left and finds a person who already told him to walk to the right then he will not continue going to the person's left.
As we know the ratings of the persons and Reziba’s rating, we know the direction Chef was told by each person. Therefore, the problem is to find out whether Chef, after being directed by some person, for example, to go left, will pass that person again going right; that is, there is a rating that is lower somewhere later in the sequence.
Formalizing what was said above, if for some i we have A_i>R, for any j>i it should be A_j < A_i. Similarly, if for some i A_i < R, for any j > i it should be A_j > A_i. It is clear that for each i, the constraints on A_i have the form X_i < A_i < Y_i, where
X_i = max \{A_j : j < i, A_j < R\}
X_i = min \{A_j : j < i, A_j > R\}
We can process the ratings one-by-one, maintaining X_i, Y_i (in editorialist’s solution they are named min_rating and max_rating) and checking the constraints one-by-one.
The solution works in O(N) time, because we do a constant amount of operations for each input rating, and requires O(1) additional memory (apart from O(N) memory to store the input array) because we use a constant amount of variables.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.