Utsavcc's blog

Help needed in a DP Problem
By Utsavcc, history, 8 days ago, In English

Given an array of length N with elements array[i] (negative integers inclusive), maximize the Score of the array.

Score of the array = -seg[1]+seg[2]-seg[3]+seg[4].... where all seg[i] are the sum of non-intersecting segments of the array which constitute all of the array when combined. We are also provided with an integer K, meaning the array must be divided exactly into K segments.

We aren't given constraints in the problem statement. What is the optimised approach for this question.

Could anyone share the solution with DP state[N][K]

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
8 days ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

I guess yes? the DP state is $$$dp[i][j]$$$ meaning that the optimal score of the array when considering index i and we already have j segments. Initially, $$$dp[0][0]=0$$$ and for every i and j we have: dp[i][j]=dp[i-1][j-1]+(-1 if j%2 else 1)*a[i] (start a new segment for a[i]) and: dp[i][j]=dp[i-1][j]+(-1 if j%2 else 1)*a[i] (append a[i] to previous segment) This will give a time complexity of $$$O(n^2)$$$ . Correct me if I'm wrong I'm also a newbie in CP...

  • Edit 1: bad display
  • Edit 2: (j-1)%2 to j%2.
→ Reply
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please Exaggerate.

    → Reply
    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Large block of text
      → Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

its not dp simple greedy

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

    I guess finding the minimal elements and assign them to the $$$k/2$$$ negative sign intervals will be achievable?

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

      didn't get what you are trying to say but greedy is

      assume if 1st element is negative then simply answer is sum of absolute value of all elements

      otherwise we give seg1 to any prefix and it it benificial to end prefix in such a place such that seg2 starts with positive elements then we can just take absolute of all values from that index so just find maximum of sum(pref[i])+sum(suff[i+1]) for all i where suff[i] contain sum of absolute values of suffix from i to n and pref[i] is sum of from 1 to i

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

      if you want to do it with dp you can use dp[i][0] and dp[i][1] where 0 represents negative and 1 represents positive then

      dp[i][0]=-a[i]+max(dp[i-1][0],dp[i-1][1])

      dp[i][1]=a[i]+max(dp[i-1][0],dp[i-1][1])

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

    We have to divide the array mandatorily into K segments

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

      i guess greedy works

      → Reply
      • »
        »
        »
        »
        8 days ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Explain the approach. I assume you think we can change segment so as to add negative number positively into our sum and accordingly change the segment again to add positive numbers as it is into our sum, but we should take into consideration that there is a condition to divide array into K segments only.

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

          oh sorry i missed we have to cut it in exactly k segments

          → Reply
»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Maybe the state of dp[i][j][k] works? i meaning ending at index i, j meaning last idx of start of current segment and k meaning remaining segments.

→ Reply
»
8 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I tried it with a 3d dp way with states as current index , number of segments left and a flag variable of wheather segment is ending here or not. it is much like a knapsack dp problem with some variation

my recursive dp solution — https://p.ip.fi/33m8

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

    Using flag is not preferrable since it gives WA. The index where the segment started is more preferrable instead.

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

      I don't think so do itself. Takes care of the best possible combination when I reach some state and states are dynamic in both cases If you have any counter test case please refer it

      → Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

very simple dp, let dp[i][k] be maximum score made up to index i with k segments, now if k is pair means you will take max of dp[j][k-1]-pref[j-1],1<=j<i(use 1 indexed for prefsum) else take maximum dp[j][k-1]+pref[j-1], then score if k is pair you add pref[i] to that max chosen else you minus pref[i], now to in order not to loop over all j's u can use map such that map1[k] is max dp[j][k-1]-pref[j-1] and map2[k] is max dp[j][k-1]+pref[j-1],i hope u understand my explanation.

→ Reply