Please help me with this problem. Time limit is 1s. Thanks!
# | User | Rating |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | -is-this-fft- | 148 |
5 | atcoder_official | 148 |
5 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
9 | TheScrasse | 144 |
Please help me with this problem. Time limit is 1s. Thanks!
Name |
---|
Not an Expert in this, but I think Ternary Search + DP might work (open to suggestions and discussions), here is how it goes. Proof: While calculating dp[i], we obviously will look after the prefix of array from arr[0] to arr[i-1]. Now the dp values will always be monotonously increasing from dp[0] to dp[i-1], also if we want to minimize dp[i] = dp[j] + (arr[i]-arr[j])^2 + C, where 0=<j<i then you see there are two parameters. One parameter is the squared difference between the elements and another parameter being the dp value at the selected index. The difference increases as we go from i-1 to 0 (since array is sorted) but dp values increase as we go from 0 to i-1 (as we discussed before monotonously increasing). So technically there must be an index j between 0 and n-1 (both inclusive) where the net value (sum of both parameters) is minimized. So we can ternary search over that prefix and do this till we obviously reach last index and dp[n-1] will be our required answer.
Sample test case might help :)
If I am not wrong this problem can be solve using convex hull optimization or Li chao tree. you can check this video https://www.youtube.com/watch?v=DknbfinVLLk&t=1924s for reference