harshit2202's blog

Another DP Problem
By harshit2202, history, 6 years ago, In English

Problem Statement

Unable to solve the problem Editorial is also not available . Can anybody explain? Thanks in advance:)

Tags #dp
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Store an array b where b[i] is the sum of all aj = i

So in the sample, b would be {2, 10, 6}, the problem turns into a simple DP problem, if you are at state i you have 2 options:

1) leave b[i] and move to state i + 1

2) take b[i] and move to state i + R + 1

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

    Giving WA:(

    It will be wrong for test case 1 2 1 2 1 3

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

      Sorry missed one more thing, you should set R = min(L, R)

      because if you start taking elements in increasing order, then the difference between every consecutive values should be at least R

      and if you start taking elements in decreasing order, then the difference between every two consecutive values should be at least L

      The optimal solution is to choose the order which gives the minimum difference between consecutive values which is min(L, R)

      code

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

        Thanks:) Got it.

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

        hey mate can u explain why it should be min(l,r) and not max(l,r)?? update :-> i got it,still thanks!!

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

        It can be done with this way as well: do DP twice..from index 0 and going to right with distance R and from index 1e5 with distance L, then pick the maximum of the two values obtained.

        → Reply