CLRL - Editorial
#PROBLEM LINK:
[Practice][111]
[Contest][222]
**Author:** [Full name][4444]
**Tester:** [Full name][5555]
**Editorialist:** [Alexander Kulkov][6666]
#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), array) because we use a constant amount of variables.
#AUTHOR'S AND TESTER'S SOLUTIONS:
Author's solution can be found [here][333].
[here][333].<br>
Tester's solution can be found [here][444]. [here][444].<br>
Editorialist's solution can be found [here][555].
[here][555].<br>
#RELATED PROBLEMS:
[111]: http://www.codechef.com/problems/CLRL
[222]: http://www.codechef.com/NOV17/problems/CLRL
[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server
[555]: https://pastebin.com/jffPE4s8
[4444]: http://www.codechef.com/users/author_nick
[5555]: http://www.codechef.com/users/tester_nick
[6666]: http://www.codechef.com/users/melfice