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:

  • DPi,j: the minimum sum of absolute differences for the ith integer in the array with a subsequence of length j.

Then, for each given state, consider choosing any integer in the array before the ith one:

Thus, DPi,j=min(DPk,j1+|AiAk|), where 1k<i and |AB| represents the absolute difference between A and B.

Time Complexity: O(N2K)

Subtask 2

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

  • Maintain K for all integers that come before i but have AkAi with min(DPk,j1Ak) at the Akth index.
  • Maintain K for all integers that come before i but have Ak>Ai with min(DPk,j1+Ak) at the Akth index.

Then, for each given state, DPi,j=min(query_smaller(Ai)+Ai),query_bigger(Ai)Ai), where query_smaller(IDX) returns the minimum min(DPk,j1Ak) for all indices less than or equal to IDX and query_bigger(IDX) returns the minimum min(DPk,j1+Ak) for all indices greater than IDX.

Time Complexity: O(Nlog(N)K)


Comments

There are no comments at the moment.