### venti's blog

By venti, history, 8 months ago,

Reading through this DP blogpost by zscoderhttps://codeforces.com/blog/entry/47764

In the "open and close interval" section, the blogpost explains this problem — https://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!

•  » » 8 months ago, # ^ |   0 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?
 » 8 months ago, # |   0 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