Excellent Programming Problems and Ideas

Record some brilliant problems and ideas I met.

Dora and Search·

• The problem is to find in a permutation of $n$ numbers a subsegment such that the leftmost and rightmost elements are not the maximum or the minimum in the subsegment.
• My brute force idea is, for each element in the permutation, to find the nearest one on the left which is bigger than itself, the nearest one on the left which is smaller, the nearest one on the right which is bigger and the nearest one on the right which is smaller. According to them we can easily determine the left and right boarder $l$ and $r$ for some element $a_i$ such that $a_i$ is not the maximum or the minimum in both the range $a_l \cdots a_i$ and $a_i \cdots a_r$. Let’s denote the $l$ and $r$ for $a_i$ as $l_i$ and $r_i$.
• Then, we can iterate $l$ from $1$ to $n$ and find $t = \max_{k \in [r_l, n]} l_k$. If $t >= l$, we can make sure that $\left[l, \arg \max_{k \in [r_l, n]} l_k \right]$ is a valid subsegment.
• The official solution is much simpler. We start from the whole segment $[1, n]$, and each step if one of the two ends of the segment does not meet our requirements we can directly remove it. Then we will get some valid solution or there is no valid subsegments.
• The correctness is quite obvious. If one end does not meet the requirements, for example, the leftmost element is larger than all the other elements, then every subsegment containing the leftmost element (which must start from the left end) should be invalid. So we can directly delete this element and look for our solution in the remaining numbers.