retired_'s blog

Need help in a DP problem
By retired_, history, 5 years ago, In English

This is a problem from HackerEarth March Easy'20.
Problem link
Any help will be appreciated!

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

.

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

    I think you misunderstood the problem.
    If we have given money to some agent and bought a house from him then we don't have to pay him again if we buy another house lying in that agents' range. Although we may have to pay some other agents who are also selling that new house.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      SORRY what I wrote before isn't true

      I don't know how to solve this problem faster than O(n^3)

      cost[l][r] = sum of the costs of the agents whose intervals are completely included in [l,r]

      d[j][i] = the maximum profit that you can make by "not buying" i-j houses out of the first i IF you buy the ith house

      d[j][i] = max(d[j-1][i-1], max{d[j-1][k] + cost[k+1][i-1] | k < i-1})

      the answer is cost[1][n]-d[k][n]

      you can calculate d[][] in O(n^3), but I think that if you fix j, and take i < z:

      let a be the index (a < i) for which you get the maximum value for d[j][i]

      let b be the index (b < z) for which you get the maximum value for d[j][z]

      then a < b? if this is true, then you can use divide et impera to calculate d[][] in O(n^2*logn)

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

        Thank you! As per the editorial of this problem we can use CHT to optimize DP.
        I guess i need to learn how to use CHT first.

        → Reply