DreamingBoy's blog

Hard DP problem.
By DreamingBoy, history, 8 years ago, translation, In English

Hi CodeForces.

I won't give link of problen and explain statement of problem, because this problem has more easier solution. But i want implement my solution idea, but i have problems with realization, and i need your help.

In problem i must calculate dp

like

I think, exist way to calculate dp mush faster -> dp[i] = max(dp[j - 1] + (mx[j] - mn[j])) 1 <= j < i

mx[j] -> maximum from j to i

mn[j] -> minimum from j to i

Thanks in advance!

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

Comments Comments (4)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Nevermind, i was wrong :D. Even though the optimal j's are increasing, the recurrence function might have several local maximum values.

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

I think I have a really nice idea, but I'm not sure it works. I'll try implement it, but please provide a link to reassure the correctness. I really want to see with my own eyes that it works. The task is very interesting because at first glance it seems just some usual dp, and then you have no idea how to continue the optimization.

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

    :)

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

      Ok, thanks. I see that I once read the task(actually during the contest) but didn't upsolve it. So before implementing my current idea, I took a look at the editorial because I saw that a lot of people solved it and I thought (and I was right) that I miss something and my solution is overcomplicated. I guess that since you asked about it on forum you've already read the editorial and didn't understand. The key observation is that every segment in the optimal solution would consist of a monotonic sequence(that is either increasing, either decreasing). Why is that? You can prove it easily by considering a point i inside the segment that has a[i — 1] > a[i] < a[i + 1] or a[i — 1] < a[i] > a[i + 1]. For simplicity, let's suppose we already proved the statement for smaller lengths and there is at most one such point. if you cut the string before i, or immediately after i, you'll get a better total cost. So now everything that needs to be done is to use this observation. For that matter, you can just consider the cost of some interval [i, j] as |a[i] — a[j]| because in any such interval, |a[i] — a[j]| <= cost (so you won't get a solution better than the optimal one) and the optimal one will be taken into consideration (because the intervals that make up the partition are monotonic so the cost in that case is going to be exactly |a[i] — a[j]|). For doing that it is enough to use the recurrence dp[i] = max (dp[j] + a[i] — a[j + 1], dp[j] + a[j + 1] — a[i]) (and that is from a similar way of thinking, because max (x — y, y — x) = |x — y| so, again, you won't miss the solution). Using this reccurence, we get O(N) complexity.

      → Reply