How to interpolate on lagrage speedup trick
Разница между en1 и en2, 362 символ(ов) изменены
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 is 
12, we get 4 segments.↵
But when C is 
2, 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 arra
y. 

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский errorgorn 2019-09-07 15:45:50 25 Tiny change: ' lagrange speedup t' -> ' lagrange (or aliens) speedup t'
en7 Английский errorgorn 2019-09-07 14:27:15 0 (published)
en6 Английский errorgorn 2019-09-07 14:22:20 7 (saved to drafts)
en5 Английский 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 Английский errorgorn 2019-09-07 14:14:07 1 Reverted to en2
en3 Английский errorgorn 2019-09-07 14:12:08 1 Added question mark on title
en2 Английский errorgorn 2019-09-07 14:11:22 362 (published)
en1 Английский errorgorn 2019-09-07 14:03:28 1570 Initial revision (saved to drafts)