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.

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

Observe that a value $$$x$$$ could be the final value iff $$$x \leq \min A$$$ AND $$$x$$$ is the gcd of some non-empty subset of $$$A$$$.

For the latter condition to hold, $$$x$$$ must be a divisor of at least one value $$$A_i$$$. Also, if $$$[A_a, A_b, ..., A_c]$$$ are all the values of $$$A$$$ divisible by $$$x$$$, their collective gcd must be equal to $$$x$$$.

Thus we can iterate through the divisors of each $$$A_i$$$ and maintain a hashmap, mapping a divisor to the collective gcd of its multiples in $$$A$$$, then count the number of divisors that satisfy.

Time complexity: $$$O(N (\sqrt M + D \log M))$$$, where $$$M = \max A$$$ and $$$D$$$ is the maximum number of divisors for a value $$$A_i$$$, which can be considered roughly $$$O(M^{1/3})$$$.