PROBLEM LINK:Author: Abizer Lokhandwala 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 onebyone, 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 EXPLANATION:When can we conclude that the sequence has mistakes? In problem statement, there is only one constraint:
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 onebyone, maintaining $X_i$, $Y_i$ (in editorialist's solution they are named $min$_$rating$ and $max$_$rating$) and checking the constraints onebyone. 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. RELATED PROBLEMS:
This question is marked "community wiki".
asked 11 Nov '17, 22:57
