venti's blog

Open-and-close-interval DP doubt
By venti, history, 4 years ago, In English

Reading through this DP blogpost by zscoder — https://mirror.codeforces.com/blog/entry/47764

In the "open and close interval" section, the blogpost explains this problem — https://mirror.codeforces.com/contest/626/problem/F

The explanation says -

"Suppose there are j open sets. When we add a[i], the sum a[i] - a[i - 1] will contribute to each of the j open sets, so we increase the current imbalance by j(a[i] - a[i - 1])."

But doesn't this imply that all j open sets contain a[i-1]?

Shouldn't the correct net increase in imbalance be - sum(a[i] - max(cur_open_set)) // (assuming we somehow tracked the max for each cur_open_set)

But for my equation to be equal to j*(a[i]-a[i-1]), all the current open sets would need to have a[i-1] in them. So how does this work?

Basically I'm unable to understand the transition of the 3rd state in the DP equation in the blogpost. If anyone can help clarify my misunderstanding or explain it in a different way, I'd be grateful!

Please help! Thanks!

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

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

But doesn't this imply that all j open sets contain a[i-1]?

Let me answer this question — suppose your group contains students a[1], a[3], a[5]. In this case your imbalance is a[5]-a[1] which you can also write as (a[2]-a[1])+(a[3]-a[2]) + (a[4]-a[3]) + (a[5]-a[4]). So you can see even though your set doesn't contain a[4] and a[2], you can still use them to calculate the final answer. The only two elements which needs to be in any set is where a set begins or a set ends.

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

    Okay, so in your example, for dp[4][1][k], only because we're transitioning from k = (a[4]-a[1]) to new_k = k + 1*(a[5]-a[4]), we can assume that the group (a[1], a[3]) has the pre-existing imbalance of (a[4]-a[3]) + (a[3]-a[2]) + (a[2]-a[1]). Correct?

    i.e. we can only make this transition of adding j*(a[5]-a[4]) when the dp state is dp[i][j][x] where x = a[4]-a[1]. Correct?

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

no, take the example problem and the array $$$(1,2,3,4,5,6,7)$$$ ,lets say we are processing the third element and we have open currently open sets $$$(1),(2)$$$,lets see what happens to the sets we dont close

  • add $$$3$$$ to $$$(2)$$$ and keep it open

  • add $$$4$$$ to $$$(2,3)$$$ and keep it open

look at the first set , after we add 3 ,the answer must increase by 3-2 even though we haven't done anything to it . after we add 4 ,the answer must increase by 4-3. we are basically saying that in the first set $$$(1,????)$$$ the last number we add to this set before we close it must be at least 1 + (3-2) + (4-3) since we are processing the array in increasing ,2 and 3 doesn't have to be neccesarily in it

But doesn't this imply that all j open sets contain a[i-1]?

so no , the point of open close interval trick is that the changes to the intervals are global so you don't have to keep track of each individual interval when a change happens

→ Reply