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}$ ~DP_{i, j}~: the minimum sum of absolute differences for the $i^\text{th}$ ~i^\text{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^\text{th}~ one:

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

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

Subtask 2

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

Maintain $K$ ~K~ for all integers that come before $i$ ~i~ but have $A_k \le A_i$ ~A_k \le A_i~ with $\min(DP_{k, j-1} - A_k)$ ~\min(DP_{k, j-1} - A_k)~ at the $A_k^\text{th}$ ~A_k^\text{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(DP_{k, j-1} + A_k)~ at the $A_k^\text{th}$ ~A_k^\text{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)$ , where $\text{query_smaller}(IDX)$ ~\text{query_smaller}(IDX)~ returns the minimum $\min(DP_{k, j-1} - A_k)$ ~\min(DP_{k, j-1} - A_k)~ for all indices less than or equal to $IDX$ ~IDX~ and $\text{query_bigger}(IDX)$ ~\text{query_bigger}(IDX)~ returns the minimum $\min(DP_{k, j-1} + A_k)$ ~\min(DP_{k, j-1} + A_k)~ for all indices greater than $IDX$ ~IDX~.

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

Comments

There are no comments at the moment.