Official

S - 絶対値/Absolute Value Editorial by maspy Editorial for printing

[1] Maximizing absolute values

When maximizing an absolute value, the following transformation is sometimes useful:

\[ |x|=\max(x,-x) \]

In this problem, the answer can be interpreted as follows:

  • Choose a subsequence \((B_0,B_1, \ldots, B_{M-1})\) of \((A_L, \ldots, A_R)\) with length at least \(3\).
  • Also choose signs \(s_0,s_1,\ldots,s_{M-3}\) (\(s_i\in \lbrace -1,1\rbrace\)).
  • Define the score as \(\sum_{k=0}^{M-3}s_k(B_k+2B_{k+1}+3B_{k+2})\). The answer is the maximum possible score.

In other words, we allow each \(s_k\in \lbrace -1,1\rbrace\) to be chosen freely, regardless of the sign of \(B_k + 2B_{k+1} + 3B_{k+2}\).

[2] A solution using DP

First, consider solving the problem once for the sequence \(A\).

Viewing the problem as choosing a subsequence \(B\) and a sign sequence \((s_i)\) consisting of \(\pm 1\), we can solve it using DP. After choosing through \(s_i,B_i\), keep the last \(2\) selected signs \((s_{i-1},s_i)\) as the state, with all contributions to the score from elements through \(B_i\) already computed.

We need special handling near the beginning and end. Accounting for this, we can use, for example, the following \(10\) states:

  • Before starting: \(1\) state in which no element has been selected.
  • Just after starting: \(2\) states corresponding to the choice of the first \(s_i\).
  • Normal states: \(4\) states remembering the last \(2\) signs \(s_i\).
  • Just before finishing: \(2\) states in which the last \(s_i\) has been chosen and elements through \(B_{i+1}\) have been selected.
  • Finished: \(1\) state in which all \(s_i, B_i\) have been selected.

[3] Processing queries with a segment tree

This gives a DP with \(K=10\) states for a single answer query. The DP transition for processing each element can be represented by a \(10\times 10\) max-plus matrix, so storing each element’s transition matrix in a segment tree solves the problem. The time complexity is \(O(NK^3 + QK^3\log N)\).

[4] Further reading: Faster answer queries

Let \(M_1, \ldots, M_n\) be the matrices stored in the segment tree nodes accessed by an answer query. Ultimately, we need only one entry of the matrix product

\[ M_1M_2\cdots M_n \]

Here, each \(M_i\) is a \(K\times K\) matrix stored at a node of the segment tree.

Thus, we do not need the matrix product itself to obtain the answer. It is enough to compute

\[ vM_1M_2\cdots M_n \]

for a row vector \(v\). Instead of computing this product as

\[ v(M_1M_2\cdots M_n) \]

consider computing it from left to right as

\[ (\cdots((vM_1)M_2)\cdots M_n) \]

Then an answer query can be processed by repeated vector-matrix products instead of matrix-matrix products. This improves the time complexity of an answer query from \(O(K^3\log N)\) to \(O(K^2\log N)\).

There have been previous problems requiring this kind of optimization, for example when \(K\) is larger than in this problem and most queries are answer queries.

However, this optimization is not available through AtCoder Library’s standard API.

posted:
last update: