@taran_1407 please elaborate the observation 2 in the last question!
Here, im going to explain the second observation in @mgch’s solution.
Take an example, given a set {a,b,c,d} (assume a< b< c< d for sake of simplicity)
Let us assume that a group of 4 leads to optimal solution.
Then the cost of above set will be |b- a| + |c - b| +|d -c|.
But, another possible arrangement is to connect a with b and c with d, creating two groups {a,b} and {c, d}
In this arrangement, cost will be |b-a| + | d-c|
This way, cost of second arrangement is less than cost of first arrangement by |c-b|.
This contradict our assumption that a group of 4 can result in optimal solution.
So, optimal solution contains only groups of 2 and 3 (only 1 group of 3 in case size of given set is odd).
Hope it makes everything clear.
1 Like
@taran_1407 thanks a lot!
one more thing please…it is written : “(min and max on the segment in the segment tree, dp[2][2], dp[2][2] and other things)”. What is the need to store min and max? We can calculate dp values by hand at base level and thus can combine them to get answrs for higher level. so, what is the need for them?
and last thing i have understood how to add elements(just add a node at last) but how to support erase operations? is min and max is something that requires for this one?
Mate, i haven’t myself implemented the solution yet. I knew about 2nd observation, so i wrote the proof here…
okay thanks taran but one request if you implement it in future please provide the solution link.
If i implement, i will post solution link.