You are not logged in. Please login at www.codechef.com to post your questions!

×

CLRL - Editorial

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 11 Nov, 22:57

melfice's gravatar image

2★melfice
412
accept rate: 0%

edited 14 Nov, 19:29

admin's gravatar image

0★admin ♦♦
16.9k347485513

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,984
×1,108
×247
×6

question asked: 11 Nov, 22:57

question was seen: 73 times

last updated: 14 Nov, 19:29