ConvexSequence
SRM 518 · 2011-05-25 · by omeometo
Problem Statement
A sequence x[0], ..., x[N-1] of integers is called convex if for every 1<=i<=N-2, x[i-1]+x[i+1]>=2*x[i]. For example, sequences 7,3,4,5,7 and 4,2,1,3 are convex, while 4,3,1,2 and 5,7,3 are not. A sequence with one or two elements is always convex.
You are given a
Constraints
- a will contain between 1 and 50 elements, inclusive.
- Each element of a will be between 0 and 10^9, inclusive.
{6,5,1,5,3,3}
Returns: 7
You can change the given sequence into a convex sequence by seven operations: doing the operation on a[1] twice, on a[3] four times and on a[4] once yields a convex sequence 6,3,1,1,2,3.
{3,0,1,4}
Returns: 0
No operation is needed; the sequence is already convex.
{1,1,1,0,2,2,2}
Returns: 5
You can change the sequence into 1,0,0,0,0,1,2 by five operations.
{854159326, 317144183, 781399725, 287076509, 894967145, 882577367, 174517516, 134415519,
274494874, 709819883, 59717133, 732212854, 40551288, 232526958, 811785438, 930853743,
946882902, 321325300, 397702677, 376192501, 599310562, 889156198, 135776890, 882710939,
823196361, 681959076, 318666702, 94469186, 536320456, 116468376, 530320850, 436708006,
903344748, 659080120, 774722507, 967315412, 566063635, 43970906, 497687103, 781266213,
876086123, 366960001, 587364849, 191948103, 172568553, 539762057, 83507466, 71569625,
686305822, 663789601}
Returns: 20178337330
{0,4,4,4,9,9,9}
Returns: 12
The following solution is wrong: "First calculating real convex hull then replace each segment with sequence of the form (a,a+b,a+2b,...,a+kb,a+kb+(b-1),a+kb+2(b-1),...,a+kb+l(b-1))". It gives (0,*,*,4,*,*,9)->(0,1,2,4,5,7,9), which is not convex.
Submissions are judged against all 170 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ConvexSequence with a public method long long getMinimum(vector<int> a) · 170 test cases · 2 s / 256 MB per case