Editorial for Max's Anger Contest Series 1 P5 - Slacking Subsequences - Olympiads Online Judge

Editorial for Max's Anger Contest Series 1 P5 - Slacking Subsequences

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

Subtask 1

Realize a DP state:

$DP_{i, j}$ $D P_{i, j}$ : the minimum sum of absolute differences for the $i^\text{th}$ $i^{th}$ integer in the array with a subsequence of length $j$ $j$ .

Then, for each given state, consider choosing any integer in the array before the $i^\text{th}$ $i^{th}$ one:

Thus, $DP_{i, j} = \min(DP_{k, j-1} + |A_i - A_k|)$ $D P_{i, j} = min (D P_{k, j - 1} + | A_{i} - A_{k} |)$ , where $1 \le k < i$ $1 \leq k < i$ and $|A - B|$ $| A - B |$ represents the absolute difference between $A$ $A$ and $B$ $B$ .

Time Complexity: $\mathcal{O}(N^2K)$ $O (N^{2} K)$

Subtask 2

Realize that the transition can be optimized with $2K$ $2 K$ Fenwick trees or $2K$ $2 K$ segment trees:

Maintain $K$ $K$ for all integers that come before $i$ $i$ but have $A_k \le A_i$ $A_{k} \leq A_{i}$ with $\min(DP_{k, j-1} - A_k)$ $min (D P_{k, j - 1} - A_{k})$ at the $A_k^\text{th}$ $A_{k}^{th}$ index.
Maintain $K$ $K$ for all integers that come before $i$ $i$ but have $A_k > A_i$ $A_{k} > A_{i}$ with $\min(DP_{k, j-1} + A_k)$ $min (D P_{k, j - 1} + A_{k})$ at the $A_k^\text{th}$ $A_{k}^{th}$ index.

Then, for each given state, $DP_{i, j} = \min(\text{query_smaller}(A_i) + A_i), \text{query_bigger}(A_i) - A_i)$ $D P_{i, j} = min (query_smaller (A_{i}) + A_{i}), query_bigger (A_{i}) - A_{i})$ , where $\text{query_smaller}(IDX)$ $query_smaller (I D X)$ returns the minimum $\min(DP_{k, j-1} - A_k)$ $min (D P_{k, j - 1} - A_{k})$ for all indices less than or equal to $IDX$ $I D X$ and $\text{query_bigger}(IDX)$ $query_bigger (I D X)$ returns the minimum $\min(DP_{k, j-1} + A_k)$ $min (D P_{k, j - 1} + A_{k})$ for all indices greater than $IDX$ $I D X$ .

Time Complexity: $\mathcal{O}(N \log(N) K)$ $O (N \log (N) K)$

Comments

There are no comments at the moment.