Zumi's Blog

#training #apio #english #anhMinh

Warning: If you want to try solving the problems, skip reading everything but the statements! Also, for hints, read slowly from top to bottom of each problem.

I didn't attend the class directly, but did the problems while going on a bus to Ninh Binh. The problems were somewhat exciting to me.

A. Sorting

Statements

You are given a permutation \(A[1\dots n]\), along with \(Q\) queries, each of the form \(l, r\) which you should sort the subarray \(A[l..r]\) increasingly or decreasingly. After all the queries are processed, print the middle value \(A[N / 2 + 1]\).

Contraints

\(1 \le N \le 10^5\), \(1 \le Q \le 10^5\), \(N\) is odd.

One problem from the past

The statements reminds me of a past problem I did on Codeforces. I didn't remember the source, but in short you are given a Latin string with the same sorting queries, and then you have to return the whole string. It was feasible to solve the problem in \(O(Q \times 26 \times log(N))\) time because of the limited alphabet size.

The main idea is, for each \(l, r\) query, count the number of instances of each character in the range. Then we can re-assign the characters' positions, from the smallest to the largest. To efficiently do range-counting and range-assignments we can maintain 26 interval trees, with lazy update.

However, the problem I faced yesterday was different: the alphabet size is much bigger. Perhaps a different approach was needed. Or maybe not?

The alphabet size

From the previous problem, we know that the problem can be solved efficiently if the alphabet size was small. “Is there anyway to make the numbers pool smaller?” – that was the first question that came to my mind.

The above problem somewhat resembles radix sorting, so of course it can also be applied to numbers. However splitting digits is not eligible, as reordering still takes too much time. We need to transform numbers into something that's both small in size and easy to reassign, maybe not even caring about its original value.

The problem only asked for one element. What if, all we care about is the element itself?

Relative ordering

It turns out that we don't actually need to sort the elements. Not entirely.

Let's choose a pivot, \(X\). We transform every number larger than \(X\) to \(1\), and the rest to \(0\). Sorting becomes wrong now, but the order relative to \(X\) isn't: If we sort \(l, r\) increasingly, every number that's smaller than \(X\) still stays on the left of those which are larger than \(X\). Therefore, this masked ordering isn't entirely wrong, because the correct ordering have the same mask, and we can assume that the unlerlying original values are on the correct positions. Of course, we don't need to care about it.

Of course, since the numbers are binary now, performing the above algorithm becomes a breeze.

After all the sortings, we get the middle number's mask. It doesn't give us the answer immediately, but it does leave a hint: If the number is 1 then the answer is larger than \(X\), and vice versa.

Binary Search

To effectively use the previous hint, we can perform binary search on the value of \(A[N / 2 + 1]\), checking whether it's larger than the middle value, and shorten the range according to the answer. That is also the final missing piece to solve the problem, giving us an \(O(log(N) \times Q \times log(N))\) algorithm.

B. Zigzag

Statements

You are given an array \(A[1..N]\) of distinct numbers. There are also \(Q\) queries, each of the form \(x y\) that asks you to change the \(x\)-th number to \(y\). It is guaranteed that after each query the array always contains dintinct numbers. After each query you have to return the largest alternating subsequence of the array.

Constraints

\(1 \le N \le 10^6\), \(1 \le A[i] \le 10^9\)

Alternating Subsequence

The first thing to do is analyzing the longest alternating subsequence problem. It turns out that it is not as difficult as it sounds, in fact it can be greedily built from an array with distinct numbers.

One nice observation from the problem: If there exists such \(i\) that \(A[i – 1] \le A[i] \le A[i + 1]\), then there always exists an optimal subsequence without \(A[i]\). Why? Since they're consecutive numbers, \(A[i – 1]\) is always better than \(A[i]\) as a “lower” number, and \(A[i + 1]\) is always better than \(A[i]\) as an “upper” numbber. Therefore, it is safe to just remove \(A[i]\) from the array without losing the optimal sequence.

Now let's continuously remove such numbers from the array until there is no such one. Which means, for each \(i\), it is either \(A[i – 1] \le A[i] \land A[i] \ge A[i + 1]\) or \(A[i – 1] \ge A[i] \land A[i] \le A[i + 1]\). Wait... Isn't \(A[..]\) now already an alternating sequence? More than that, \(A[..]\) is an optimal longest alternating subsequence of the original array.

Dive a little deeper, we will find out that each \(A[i]\) can be a part of the new array if and only if has the same above atrribute on the original array. Unless it's the first or last number of the array, in such case it's always included.

Testing an element

With the above observations, we can deduce whether an element will appear in our optimal subsequence: – It's the first or last element, or – Either it's both smaller or both bigger than its neighboring elements.

Using these conditions we can check each element in \(O(1)\). To answer the length of the optimal subsequence one only has to count how many elements satisfies the above conditions.

Processing queries

If we change one number, how is each element's satisfiability affected? It turns out, only 3 of them are affected at most: the element itself, and its neighboring elements.

It is now easy to process each query in \(O(1)\): just change the element and re-check every affected elements.

That concludes our \(O(N + M)\) algorithm.