Introducing Reverse Operations

This is sudden, but what approach would typically be used if the operations were assignments rather than chmax and chmin? The key is to consider reverse operations. The correspondence between assignment and its reverse operation is as follows.

• Assignment: set \(z\) to \(q\). The result is \(z=w\).
• Reverse assignment: assuming that \(q\) matches \(w\), replace \(w\) with \(\ast\). As a result, \(z\) matches \(w\).
  • We say that \(\alpha\) matches \(\beta\) if \(\alpha=\beta\) or \(\beta=\ast\) holds.

More generally, when considering a sequence of operations, the correspondence is as follows.

• Looking at the operation sequence from the beginning: apply a prefix of the operation sequence to the initial state to obtain the current state. The state reached at the end matches the target state.
• Looking at the operation sequence from the end: determine the conditions on the current state under which applying a suffix of the operation sequence produces the target state. The initial state satisfies the conditions obtained at the end of this process.

We can also apply this framework to our problem. The example of assignment was not chosen on a whim: a sequence of chmax and chmin operations can actually represent an assignment. For \(a\ge b\), applying chmax with \(a\) and then chmin with \(b\) is equivalent to assigning \(b\).

On closer inspection, we can sometimes represent an assignment without even combining chmin and chmax. For example, when \(z\le a\), applying chmax to \(z\) with \(a\) is equivalent to assigning \(a\) to \(z\). This suggests concepts such as “any value satisfying \(z\le a\)” or “any value satisfying \(z\ge b\),” which lie somewhere between a fixed value and the wildcard \(\ast\) that appeared in reverse assignment. If you were unsure how to begin approaching the problem, try characterizing the reverse operations of chmax and chmin, and then give the problem another try. In the next section, we will present the solution out of nowhere.

Solution to the Problem

Let us set aside the limit on the number of operations and consider whether \(A\) can be transformed into \(B\) using finitely many operations.

We look at the operation sequence from the end. Here, a state means the integer sequence of length \(N\) on which the operations are performed. We maintain integer sequences \(L=(L_1,L_2,\dots, L_N),R=(R_1,R_2,\dots, R_N)\) as conditions on the current state \(A'\). \(L,R\) represent the following: satisfying \(\forall i, A'_i\in [L_i,R_i]\) is necessary and sufficient for applying the suffix of the operation sequence determined so far to \(A'\) to produce \(B\). When the suffix determined so far is empty, we clearly have \(L_i=R_i=B_i\). Note that we are maintaining conditions on the current state, not the current state itself.

Recall that chmax \(l\) \(r\), with \(x\coloneqq X_{r-l+1}\), performs \(A_i\leftarrow \max(A_i,x)\) for each \(i\in [l,r]\). Its reverse operation can be characterized as follows.

• Applicability condition: \(x\le R_i\) holds for every \(i\in [l,r]\).
• Change to the conditions on the current state after applying it: independently for each \(i\in [l,r]\), if \(L_i\le x\) holds, set \(L_i\leftarrow -\infty\).

Recall that chmin \(l\) \(r\), with \(y\coloneqq Y_{r-l+1}\), performs \(A_i\leftarrow \min(A_i,y)\) for each \(i\in [l,r]\). Its reverse operation can be characterized as follows.

• Applicability condition: \(y\ge L_i\) holds for every \(i\in [l,r]\).
• Change to the conditions on the current state after applying it: independently for each \(i\in [l,r]\), if \(R_i\ge y\) holds, set \(R_i\leftarrow \infty\).

We have \(L_i\in \lbrace -\infty,B_i\rbrace, R_i\in \lbrace B_i,\infty\rbrace\). Here, \(\infty\) is a formal symbol denoting a sufficiently large value. If necessary, you may replace \(\infty\) with \(N\).

For each \(i\), we call the first assignment \(L_i\leftarrow -\infty\) a lower-bound relaxation for \(i\). Similarly, we call the first assignment \(R_i\leftarrow \infty\) an upper-bound relaxation for \(i\). We refer to lower-bound and upper-bound relaxations collectively as relaxations.

For each \(i\), the interval \([L_i,R_i]\) expands monotonically. Thus, once an operation becomes applicable, it remains applicable afterward. We can also see that if an applicable reverse operation does not relax an index \(i\), that same operation will never relax it, regardless of what sequence of reverse operations is performed. Therefore, we may assume that each reverse operation is performed at most once. Furthermore, applicable reverse operations may be performed in any order, and the resulting maximally relaxed conditions \((L,R)\) are uniquely determined. It is possible to transform \(A\) into \(B\) by repeatedly applying operations exactly when these \((L,R)\) satisfy \(\forall i, A_i\in [L_i,R_i]\).

We now have a straightforward solution that disregards the number of operations and the computational complexity: repeatedly perform an applicable reverse operation that has not yet been performed, as long as one exists.

Let us consider the number of operations. There is no point in performing a reverse operation that causes no relaxation. There are only \(2N\) possible relaxations in total, counting both upper-bound and lower-bound relaxations. Thus, omitting useless reverse operations naturally limits the number of operations to at most \(2N\).

Next, consider the computational complexity. For each reverse operation op \(l\) \(r\), maintain the number of indices \(i\in [l,r]\) that prevent it from being applicable. For example, when op is chmax, this is the number of indices \(i\) satisfying \(i\in [l,r], x\gt R_i\). Prepare a queue of applicable reverse operations that have not yet been performed. Whenever a reverse operation causes a relaxation, update the table of counts of indices \(i\) preventing applicability, and add any newly applicable reverse operations to the queue. Even if we update the table naively in \(O(N^2)\) time for each relaxation, there are only \(O(N)\) relaxations, so the total time is \(O(N^3)\).

The algorithm runs in \(O(N^3)\) time / \(O(N^2)\) space.