[Help] How to interpolate on lagrange (or aliens) speedup trick?

Revision en8, by errorgorn, 2019-09-07 15:45:50

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 (or aliens) 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 2, we get 4 segments. But when C is 3, 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.

For my code, the input format is:

n k

a1 a2 a3 a3... an

Where ai is the ith element in the array.

Tags convex hull optimization, lagrange, #help me


  Rev. Lang. By When Δ Comment
en8 English errorgorn 2019-09-07 15:45:50 25 Tiny change: ' lagrange speedup t' -> ' lagrange (or aliens) speedup t'
en7 English errorgorn 2019-09-07 14:27:15 0 (published)
en6 English errorgorn 2019-09-07 14:22:20 7 (saved to drafts)
en5 English errorgorn 2019-09-07 14:14:55 5 Tiny change: 'rmat is:\nn k\na1 a2 a3' -> 'rmat is:\n\nn k\n\na1 a2 a3'
en4 English errorgorn 2019-09-07 14:14:07 1 Reverted to en2
en3 English errorgorn 2019-09-07 14:12:08 1 Added question mark on title
en2 English errorgorn 2019-09-07 14:11:22 362 (published)
en1 English errorgorn 2019-09-07 14:03:28 1570 Initial revision (saved to drafts)