Example problem: (I dont have the link as this problem only exists in my school's private judge)↵
↵
We have an array of n positive intergers and we need to group them into k segments such that each element of the array is in a segment and that all elements in a segment are contigous. The cost of a segment is the sum of the numbers in the segment squared.↵
↵
We need to **minimize** the total cost of all the segments.↵
↵
Example 1, we have n=5 and k=3. Where the array is [1,2,3,4,5].↵
The optimal answer is by grouping (1+2+3) , (4) and (5) into different segments.↵
The total cost is 6^2 + 4^2 + 5^2 =77.↵
↵
Example 2, we have n=4, k=2. Where the array is [1,1000000,3,4].↵
The optimal answer is by grouping (1,1000000) and (3,4) into different segments.↵
The total cost is 1000001^2+7^2=10000200050↵
↵
Now I asked some people and they said this can be solved by doing the lagrange speedup trick.↵
We shall define a cost C. Then do a convex hull trick where we try to minimize the value of all our segments but we also add C to our cost whenever we make a new segment. Now, if C is INF, then we will only have 1 segment, while if C is 0 we will have n segments. So people claim that we can binary search on C to find some C where there will be K segments existing.↵
↵
This allowed me to AC the problem, but my solution was not always correct as the test cases were weak.↵
I thought of this test case: n=4, k=3. Where is array is [1,1,1,1]↵
Now, when C is12, we get 4 segments.↵
But when C is2, we get 2 segments onl3, we get 2 segments only. ↵
Therefore when I ran my code against this case my code printed 8, even though the answer was (1+1)^2+1^2+1^2=6.↵
↵
So I think I need someway to iterpolate the lagrange speedup trick.↵
Anyone can help? My code is [here](https://pastebin.com/2563LTZY).↵
↵
For my code, the input format is:↵
n k↵
a1 a2 a3 a3... an↵
↵
Where ai is the ith element in the array. ↵
↵
↵
We have an array of n positive intergers and we need to group them into k segments such that each element of the array is in a segment and that all elements in a segment are contigous. The cost of a segment is the sum of the numbers in the segment squared.↵
↵
We need to **minimize** the total cost of all the segments.↵
↵
Example 1, we have n=5 and k=3. Where the array is [1,2,3,4,5].↵
The optimal answer is by grouping (1+2+3) , (4) and (5) into different segments.↵
The total cost is 6^2 + 4^2 + 5^2 =77.↵
↵
Example 2, we have n=4, k=2. Where the array is [1,1000000,3,4].↵
The optimal answer is by grouping (1,1000000) and (3,4) into different segments.↵
The total cost is 1000001^2+7^2=10000200050↵
↵
Now I asked some people and they said this can be solved by doing the lagrange speedup trick.↵
We shall define a cost C. Then do a convex hull trick where we try to minimize the value of all our segments but we also add C to our cost whenever we make a new segment. Now, if C is INF, then we will only have 1 segment, while if C is 0 we will have n segments. So people claim that we can binary search on C to find some C where there will be K segments existing.↵
↵
This allowed me to AC the problem, but my solution was not always correct as the test cases were weak.↵
I thought of this test case: n=4, k=3. Where is array is [1,1,1,1]↵
Now, when C is
But when C is
Therefore when I ran my code against this case my code printed 8, even though the answer was (1+1)^2+1^2+1^2=6.↵
↵
So I think I need someway to iterpolate the lagrange speedup trick.↵
Anyone can help? My code is [here](https://pastebin.com/2563LTZY).↵
↵
For my code, the input format is:↵
n k↵
a1 a2 a3 a3... an↵
↵
Where ai is the ith element in the array.
↵
