ArithmeticSequenceDiv1
TCO18 Fun 2A · 2018-04-20 · by ltdtl
Problem Statement
An arithmetic sequence of length n is a sequence y[0], y[1], ..., y[n-1] such that for each i we have y[i] = y[0] + i*d, where d is some constant. For example, {4,5,6,7}, {1,1,1,1,1}, and {7,5,3} are arithmetic sequences.
You are given a sequence of n positive integers: x[0], x[1], ..., x[n-1]. You are allowed to change this sequence. More precisely, you may perform arbitrarily many steps. In each step you may choose any element of the sequence and change it to any integer value. (Note that the new value is not required to be positive.) The cost of each change is equal to the absolute difference between the old and the new value.
You are given the
Constraints
- x will contain betwee 1 and 100 elements, inclusive.
- Each element of x will be between 1 and 100, inclusive.
{1,3,2}
Returns: 2
One optimal solution is to change this sequence into {1,2,3}. Changing x[1] from 3 to 2 costs abs(3-2) = 1. Changing x[2] from 2 to 3 costs abs(2-3) = 1. Thus, the total cost is 2.
{1,1,1,2,3,4,5}
Returns: 3
Here an optimal solution is to change x[0] from 1 to -1 (cost 2) and then change x[1] from 1 to 0 (cost 1).
{1,2,3,4}
Returns: 0
This is already an arithmetic sequence, so the cheapest solution is to do nothing.
{1,5,2,5}
Returns: 5
{11,33,22}
Returns: 17
Submissions are judged against all 186 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ArithmeticSequenceDiv1 with a public method int findMinCost(vector<int> x) · 186 test cases · 2 s / 256 MB per case