Note that $$$N$$$ has to be read as a signed 64-bit integer type. You could check it by either doing to comparison manually, or casting back and forth between the signed 32-bit integer type.

Time complexity: $$$O(1)$$$

Simply construct a $$$W$$$-by-$$$H$$$ matrix, assign $$$B_{i, j} = A_{j, i}$$$ for all relevant $$$i, j$$$, then output it.

Alternatively, if you use Python, the numpy library installed in AtCoder gives a really short implementation, as noted in this user editorial: https://atcoder.jp/contests/abc237/editorial/3344

Time complexity: $$$O(HW)$$$

Note that for a string to be a palindrome, it must start with the same number of contiguous as as it ends with.

If there are less contiguous as at the end of $$$S$$$ than at is start, the answer is No. Otherwise, add the difference in number of as to its start, then test if it is a palindrome.

Time complexity: $$$O(|S|)$$$

There are at least two methods that could be used, a straightforward method with linked list, or a reversed method with deque.

Straightforward method with linked list:

One could make a simple linked list using two arrays, $$$pr$$$ "previous" and $$$nx$$$ "next", where $$$pr[i]$$$ is the index of the node before $$$i$$$ in the list, while $$$nx[i]$$$ is the index of the node after $$$i$$$ in the list. One node ($$$N+1$$$ is convenient for this problem, thus making $$$N+2$$$ total nodes) is reserved as the "sentinel" node, whose $$$nx[s]$$$ points to the first element, and $$$pr[s]$$$ points to the last element of the list.

Then implement as in the problem statement. For the L case you should insert the new node between $$$pr[i]$$$ and $$$i$$$ by updating the $$$pr$$$ and $$$nx$$$ arrays, for the R case, insert the new node between $$$i$$$ and $$$nx[i]$$$.

Reversed method with deque:

Consider the operations in reversed order.

L is equivalent to appending $$$i-1$$$ to the right of $$$A$$$, as $$$i$$$ is already in $$$A$$$, and everything in between was supposed to be added after $$$i$$$ in the normal order. Similarly, R is equivalent to appending $$$i-1$$$ to the left of $$$A$$$.

To efficiently perform these operations, we use a deque, that allow amortized $$$O(1)$$$ appending to either end of the logical array.

Time complexity: $$$O(N)$$$

One may think of using Dijkstra's algorithm, however the happiness increases are a problem as they are effectively a negative cost. However, Dijkstra's algorithm can still be used, provided that there is a potential function $$$\phi(i)$$$ for all vertices $$$i \in [1, N]$$$, such that:

• Let $$$C_e$$$ be the current cost of a directed edge (that may be negative) going from vertex $$$u$$$ to vertex $$$v$$$. Define the new cost $$$C'_e = C_e + \phi(u) - \phi(v)$$$. These new costs must all be non-negative for the potential function to be admissible.

• After Dijkstra's is run on the graph with these new costs, let $$$R'_v$$$ be the final cost from source vertex $$$u$$$ to the destination vertex $$$v$$$. To transform this value back to the true cost, we apply $$$R_v = R'_v - \phi(u) + \phi(v)$$$.

How do we find this potential function? Turns out the problem already gives us one; you could verify that $$$\phi(i) := H_i$$$ is an admissible potential function, leaving all new edge costs non-negative:

• If $$$H_X \geq H_Y$$$, the old cost is $$$H_Y - H_X$$$, and the new cost is $$$(H_Y - H_X) + H_X - H_Y = 0$$$.
• If $$$H_X < H_Y$$$, the old cost is $$$2(H_Y - H_X)$$$, and the new cost is $$$2(H_Y - H_X) + H_X - H_Y = H_Y - H_X$$$, which is positive.

Note that the true cost should be negated before output.

Time complexity: $$$O((N+M) \log (N+M))$$$

Recall the algorithm to find the length of the LIS (longest increasing subsequence) of an array:

• Maintain a dynamic array or ordered set $$$L$$$, that is initially empty.
• For each element $$$A_i$$$, find the index of the smallest element $$$L_j \geq A_i$$$. If it exists, replace $$$L_j$$$ with $$$A_i$$$, otherwise append $$$A_i$$$ to $$$L$$$. Note that in the dynamic array variant, this is often implemented with binary search (as $$$L$$$ would always be strictly increasing), but this is not necessary for this problem.
• The final length of $$$L$$$ is the length of the LIS.

Since we are only interested in LISes up to length $$$3$$$ and because $$$M$$$ is small, we can note that there aren't that many states $$$L$$$ could be. Thus we can use dynamic programming, where $$$dp_{i, L}$$$ is the number of sequences of length $$$i$$$ that results in a particular state of $$$L$$$. Since $$$L$$$ is an array of length up to three, one could either implement it as three dimensions (zero padding if necessary), or use hashmaps and/or bitmasks.

Note that you should only sum the final $$$dp_{N, L}$$$ where $$$|L|$$$ is exactly $$$3$$$.

Time complexity: There are $$$O(N)$$$ iterations of DP, each with up to $$$O(M^3)$$$ states for $$$L$$$, each with up to $$$O(M)$$$ transitions, so the total time is $$$O(NM^4)$$$, which should fit in the time limit.

Note that we are only interested in the position of a fixed value $$$X$$$. We can thus transform all values $$$P_i$$$ to "$$$<$$$", "$$$=$$$", or "$$$>$$$" based on their relation to $$$X$$$.

One could use a lazy segment tree where each node contains the number of "$$$<$$$", "$$$=$$$", and "$$$>$$$" in that segment. To sort a subarray, we simply query for the total number of each. We can then sort that segment by range-assigning on up to $$$3$$$ subranges.

(Alternatively, you could also use three range-sum/range-assign lazy segment trees.)

Time complexity: $$$O((N + Q) \log N)$$$

Let $$$sub_1, ..., sub_{|sub|}$$$ be all distinct palindromic substrings of $$$S$$$, this can be constructed using hashmap in $$$O(|S|^3)$$$. This problem thus amounts to finding the maximum antichain among $$$sub$$$, where the partial order relation $$$s < t$$$ holds if $$$s$$$ is a proper substring of $$$t$$$.

To do so, we can use max-flow-min-cut theorem. We could create a flow graph with the following vertices:

• $$$U_i$$$, $$$V_i$$$ for $$$i \in [1, |sub|]$$$
• $$$src$$$ (the source node), $$$snk$$$ (the sink node).

And the following edges, all with a capacity of $$$1$$$:

• $$$src \rightarrow U_i$$$, $$$V_i \rightarrow snk$$$ for $$$i \in [1, |sub|]$$$
• $$$U_i \rightarrow V_j$$$ for all $$$i, j$$$ where $$$sub_i > sub_j$$$ (in other words, $$$sub_j$$$ is a proper substring of $$$sub_i$$$)...

And here we run into a problem. $$$|sub|$$$ is $$$O(|S|^2)$$$, so there could be up to $$$O(|S|^4)$$$ edges in this graph. If this doesn't exhaust the memory limit, finding the max-flow with Dinic/Hopcroft-Karp almost certainly would exceed the time limit with $$$O(E\sqrt V) = O(|S|^5)$$$.

To reduce the number of edges in the flow graph, we could, instead of only including palindromic substrings in $$$sub$$$, include all distinct substrings of $$$S$$$. (Let's call the original set of palindromic substrings $$$pal$$$).

Our new flow graph would also have two vertices for every $$$sub_i$$$, as well as $$$src$$$ and $$$snk$$$. It would have the following edges:

• $$$1$$$-capacity: $$$src \rightarrow U_i$$$, $$$V_i \rightarrow snk$$$ only if $$$sub_i$$$ is palindromic
• We still want to allow flow from $$$U_i \rightarrow V_j$$$ for all $$$sub_i > sub_j$$$...
  • Let $$$sub_i$$$ be a substring of length $$$\geq 2$$$. Let $$$sub_j$$$ be $$$sub_i$$$ without its last character, similarly $$$sub_k$$$ is $$$sub_i$$$ without its first character. Note that all proper substrings of $$$sub_i$$$ is a substring of at least one of $$$sub_j$$$ and $$$sub_k$$$.
  • Thus we can add these edges, all infinite-capacity:
    • $$$U_i \rightarrow V_j$$$, $$$U_i \rightarrow V_k$$$ for all $$$sub_i$$$ of length $$$\geq 2$$$
    • $$$V_x \rightarrow U_x$$$ for all $$$x \in [1, |sub|]$$$. This allows flow to "continue on" to lesser substrings.

This keeps the number of edges down to $$$O(|S|^2)$$$. The final answer is $$$|pal| - maxFlow$$$.

Time complexity: $$$O(|S|^3)$$$