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 $$$LIS$$$es up to length 3, we can note that there isn'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, each with up to $$$O(M^3)$$$ states, each with up to $$$O(M)$$$ transitions, so the total time is $$$O(NM^4)$$$, which should fit in the time limit.