Titan_2003's blog

Interesting and hard OA quesn
By Titan_2003, history, 6 weeks ago, In English

Problem: Minimum Sum of Absolute Differences in Subsequences

Description:

Given an array of length N (where 1≤N≤1e5) and an integer k (where 1≤k≤50), find the minimum possible value of the sum of absolute differences of adjacent elements for all subsequences of length k.

Mathematically, for a subsequence {ai1,ai2,…,aik} where i1<i2<…<iki1​<i2​<…<ik​, we need to minimize the value of:

$$$\sum_{j=1}^k |a_{i} - a_{i-1}|$$$
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
6 weeks ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

This is a relatively standard dynamic programming problem. Let dp[i][j] represent the minimum total cost of a subsequence of length j ending on the ith element. Our transitions are simply

dp[i][j]= min k<i (dp[k][j-1]+ abs(a[k]-a[i]))

Naively this can be computed in O(N^2*K). To optimize this we can use a segment tree similar to its use in CSES pizzeria queries. This solution will run in O(NKlogN) time.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please elaborate on your solution a little further.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
      ← Rev. 4   Vote: I like it +8 Vote: I do not like it

      Sure.

      Dynamic programming:

      dp[i][0]=0 for all i (the cost of a subsequence of length 1 is zero)

      The transition represents the process of trying to add the ith element to all currently optimal sequences of length j-1 to find the minimal cost of a sequence ending in i and with length k. (Hopefully it is clear that when adding to a sequence, the only things that can affect the new cost are its current cost and the value of the last element)

      Segment Tree:

      To map this problem into the example given handle every j as its own instance of the problem, set all the values of the array to inf then start from i=0 and iterate to i=N. To find the value of dp[i][j] perform "find the lowest cost starting from a[i]" query. After processing each element perform the update "index a[i] becomes dp[i][k-1]". This is because each element can only be added to an array with elements that are before it in the array.

      You can find an explanation for how the segment tree used in the problem given here. The final wrinkle is depending on how large a[i] can be you may have to use a sparse segment tree.

      This is pretty advanced for an interview question. If you don't have a background for segment trees or dynamic programming, I would try those before returning to this problem as it is not a particularly easy example of either.

      → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For the CSES problem Pizzeria queries it is clear that for all elements before the current element, we have to search in the a[i] — i segment tree and vice versa for a[i] + i. But in this one, if we are looking for the min value in (dp[k][j-1] — a[k]), we might get index k such that a[k]>a[i] and having minimum (dp[k][j-1] — a[k]), which will be wrong. Can you elaborate on the optimisation part and on how to handle this.

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I touched on it in my response to Titan, but essentially you handle the dp transitions in order of increasing i and update the tree (which is initially filled with arbitrarily large numbers) with a[i] = dp[i][j-1] only after we have processed it.

      This way the tree will only contain elements less than the current element being processed.

      Again for each j we create a new instance of the Segment tree.

      For clarity here's my solution to the CSES problem. All we do is store the minimum to get to the left and to the right in each node in the segment tree as well as each nodes size (in terms of its range). https://cses.fi/paste/7452d61222a6b9589745b9/

      → Reply