This is an unofficial and abridged translation of Japanese editorials, since official translation is not available.

A - Not Overflow

(Original: https://atcoder.jp/contests/abc237/editorial/3337)

Just do what the problem says. Beware that \(2^{31}\) does overflow while \(-2^{31}\) does not.

B - Matrix Transposition

(Original: https://atcoder.jp/contests/abc237/editorial/3318)

Set \(B_{i,j}=A_{j,i}\) using two nested for loops. Some languages and/or libraries can also transpose a matrix in a single command.

C - kasaka

(Original: https://atcoder.jp/contests/abc237/editorial/3338)

If \(S\) consists of a only, the answer is obviously Yes. Otherwise, let \(x\) be the number of consecutive a’s at the beginning of \(S\), and \(y\) be the number of consecutive a’s at the end of \(S\). If, after adding some \(k\) a’s to the beginning of \(S\), it becomes a palindrome, then \(x+k=y\) must hold.

Thus, if \(x>y\), the answer is always No. Otherwise, the answer is Yes if and only if \(S\) becomes a palindrome after adding exactly \(y-x\) a’s to its beginning. Finding \(x\) and \(y\), adding a’s, and checking for palindrome can all be done in \(O(|S|)\), so the overall time complexity is \(O(|S|)\).

D - LR insertion

(Original: https://atcoder.jp/contests/abc237/editorial/3319)

By inverting all operations, we obtain the following equivalent problem:

Initially, \(A=(N)\). Do the following for \(i=N,N-1,\dots,1\):

• If \(s_i\) is L, insert \(i-1\) to \(A\)’s end.
• If \(s_i\) is R, insert \(i-1\) to \(A\)’s beginning.

This can be implemented with a deque (double-ended queue) in \(O(N)\).

E - Skiing

(Original: https://atcoder.jp/contests/abc237/editorial/3339)

By negating all edge weights the problem becomes single source shortest path. Dijkstra’s algorithm cannot be used immediately as there are negative weights. This can be fixed by assigning some potential to each vertex, and adding to edge weights the difference in potential of the edges’ ends, so that all weights become non-negative.

Specifically, for this problem, an admissible potential is simply \(H_i\) for vertex \(i\). For a directed edge \(i\rightarrow j\), \(H_i-H_j\) is added to its weight, so the new weight is \(0\) if \(H_i>H_j\), and \(H_j-H_i\) otherwise, which is always non-negative. Distances in this new graph \(dist'(1,i)\) for all \(i\) can now be found by Djikstra’s algorithm in \(O(M\log M)\). Distances in the original graph are given by \(dist(1,i)=dist'(1,i)-(H_1-H_i)\).

F - |LIS| = 3

(Original: https://atcoder.jp/contests/abc237/editorial/3320)

Recall that, in the classical \(O(N\log N)\) LIS algorithm, the size of the DP array is always the length of LIS so far. Therefore, in this problem, all valid states have a DP array of at most 3 integers in the range of \([1,M]\). More specifically, the DP states for this problem is:

\(dp[i][a_1][a_2][a_3]\): the number of sequences whose length is \(i\) and LIS DP array is \((a_1,a_2,a_3)\).

State transition is done exactly as in the LIS algorithm for each of the possible \(M\) integers appended to the sequence. There are \(O(NM^3)\) states in total, and each state has \(M\) transitions, making the overall time complexity \(O(NM^4)\).

G - Range Sort Query

(Original: https://atcoder.jp/contests/abc237/editorial/3341)

Consider 0-1 sequences \(A\) where \(A_i=0\) if and only if \(P_i\leq x\) for some \(x\). For two such sequences with \(x=K\) and \(x=K+1\) respectively, the only index \(i\) where the two sequences differ is where \(P_i=K\). Therefore, we can solve this problem if we can process queries on 0-1 sequences.

We only discuss sorting in ascending order below, as the case of sorting in descending order is symmetrical to it. Sorting a 0-1 sequence with \(a\) 0’s and \(b\) 1’s always results in \(a\) consecutive 0’s followed by \(b\) consecutive 1’s. Thus, sorting a range \([L,R]\) in a 0-1 sequence in ascending order can be achieved by the following operations:

• Find the sum of elements (i.e. number of 1’s) in \([L,R]\). Let the result be \(S\).
• Set all elements to 0 in \([L,R-S]\) .
• Set all elements to 1 in \([R-S+1,R]\).

A lazy propagation segment tree supports all these operations in \(O(\log N)\) each. Therefore, this problem is solved in \(O(N+Q\log N)\).

Ex - Hakata

(Original: https://atcoder.jp/contests/abc237/editorial/3321)

Let \(N\) be the number of distinct palindromic substrings, then \(N\leq|S|\), because appending a character to a string creates at most 1 new distinct palindrome.

The substring relationship is a partial order among these palindromes, for if \(S_i\) is a substring of \(S_j\), and \(S_j\) is a substring of \(S_k\), then \(S_i\) must be a substring of \(S_k\). The problem asks for the size of the largest antichain in the poset (partial order set) of palindromes. By Dilworth’s theorem, it equals to the smallest number of chains this poset can be partitioned into. This, in turn, can be found by the following bipartite graph maximum matching: create \(N\) vertices on the left and \(N\) vertices on the right, and connect vertex \(i\) on the left to \(j\) to the right if and only if \(S_i\) is a substring of \(S_j\).