Connection Status:
Competition Arena > SubarrayAverages

SubarrayAverages

TCO 2018 Fun 2B · 2018-04-20 · by lg5293

TCO 2018 Fun 2B · 2018-04-20 · by lg5293 · Math
Class Name: SubarrayAverages
Return Type: double[]
Method Name: findBest
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Li Chen has an array of positive integers. You are given its initial state in the int[] arr.

Li Chen can modify the array by repeatedly performing the following operation: Choose a contiguous subarray, and replace all values in the subarray with their exact average.

For example, if the current array is {1, 3, 2, 4}, some ways to perform the next operation look as follows:

  • Li Chen can select the first three elements, obtaining the array {2, 2, 2, 4}.
  • Li Chen can select the middle two elements, obtaining the array {1, 2.5, 2.5, 4}.
  • Li Chen can select the entire array, obtaining the array {2.5, 2.5, 2.5, 2.5}.
  • Li Chen can select the last element only, which does not change the array.

Multiple operations may modify the same indices in the given array. For example, given the array {1, 4, 2} Li Chen may use one operation to change it to {1, 3, 3} and then another operation to change this array into {2, 2, 3}.

Find the lexicographically smallest array Li Chen can obtain by performing a sequence of zero or more operations. Return a double[] with the elements of that array. (See Notes for a more precise definition.)

Notes

  • Given two different arrays S and T with the same number of elements, the lexicographically smaller one is the one that has a smaller element at the first index at which they differ.
  • Your answer will be accepted if each element of your return value has an absolute or a relative error at most 1e-9.

Constraints

  • arr will contain between 1 and 1,000 elements, inclusive.
  • Each element of arr will be between 1 and 10^6, inclusive.
Examples
0)
{1,2,3,4,5,6,7,8,9}
Returns: {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0 }

Here, Li Chen should leave the array unchanged.

1)
{7,6,5,4,3,2,1}
Returns: {4.0, 4.0, 4.0, 4.0, 4.0, 4.0, 4.0 }

In this case, Li Chen should perform one operation on the entire array. Note that the subarray chosen for each operation has to be contiguous. For example, Li Chen is not allowed to change {7, 6, 5, 4, 3, 2, 1} into {3.25, 6, 5, 4, 3.25, 3.25, 3.25}.

2)
{1,2,1,2}
Returns: {1.0, 1.5, 1.5, 2.0 }
3)
{1,10,1,1,1,1,10}
Returns: {1.0, 2.8, 2.8, 2.8, 2.8, 2.8, 10.0 }
4)
{4,5,6,7,8,9,10,11,12,13,14,15,16,17,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: {4.0, 5.0, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846, 5.846153846153846 }

Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SubarrayAverages with a public method vector<double> findBest(vector<int> arr) · 116 test cases · 2 s / 256 MB per case

Submitting as anonymous