SORTDIS Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Danny Boy
Tester: Harris Leung
Editorialist: Pratiyush Mishra, Jakub Safin

DIFFICULTY:

Easy-medium

PREREQUISITES:

Segment trees

PROBLEM:

You should perform queries on a sequence A. In each query, you either change an element A_i or need to find the smallest K such that |A_L-K|, |A_{L+1}-K|, \ldots, |A_R-K| is sorted in non-decreasing order (or determine that no such K exists).

EXPLANATION:

Let’s reformulate a condition |A_i-K| \le |A_{i+1}-K|. There are three distinct cases:

  • A_i = A_{i+1}: the condition is always true
  • A_i \lt A_{i+1}: we need K \le (A_{i+1}+A_i)/2
  • A_i \gt A_{i+1}: we need K \ge (A_{i+1}+A_i)/2

It’s easy to see because the condition says simply "K cannot be closer to A_{i+1} than A_i".

In addition, we’re looking for K \ge 0 and clearly won’t ever need K \gt M = 10^9 (M is the upper bound on elements of A). That means we can create and keep updating a new sequence of ranges [l_1, r_1], \ldots, [l_{N-1},r_{N-1}], where:

  • if A_i = A_{i+1}, then l_i = 1 and r_i = M
  • if A_i \lt A_{i+1}, then l_i = 1 and r_i = (A_{i+1}+A_i)/2
  • if A_i \gt A_{i+1}, then l_i = (A_{i+1}+A_i)/2 and r_i = M

For each query of type 1, at most two of these values need to be updated. These ranges determine allowed values of K, so in a query of type 2, we just need to find x = \max(l_L, \ldots, l_{R-1}) and y = \min(r_L, \ldots, r_{R-1}). Then:

  • if x \gt y, there is no possible K
  • if x \le y, any K in the range [x,y] satisfies the condition; we’re looking for the minimum, which is K = x

Finding the minima and maxima of ranges, along with updating single elements, is done efficiently by several well-known data structures like segment tree.

TIME COMPLEXITY:

We use two segment trees, perform O(1) operations in each tree for each query, so the time complexity is O((N+Q) \log N).

SOLUTION:

Setter’s Solution
Tester’s Solution

The solution link is not working.

1 Like

links are not working

Hey @aditya25052001 :wave:
Link is working now