Connection Status:
Competition Arena > TheProduct

TheProduct

SRM 453.5 · 2009-11-20 · by Vasyl[alphacom]

SRM 453.5 · 2009-11-20 · by Vasyl[alphacom] · Greedy, Simple Math, Sorting
Class Name: TheProduct
Return Type: long
Method Name: maxProduct
Arg Types: (vector<int>, int, int)
Problem Statement

Problem Statement

You are given an int k and a int[] numbers containing exactly N elements. Choose exactly k distinct integers between 0 and N-1, inclusive, and arrange them in ascending order. The difference between each pair of consecutive elements in this sequence must be less than or equal to maxDist. Each element in this sequence represents a zero-based index into the int[] numbers. Multiply the corresponding elements of numbers together to obtain a product. Return the maximal possible product you can get.

Constraints

  • numbers will contain between 1 and 50 elements, inclusive.
  • Each element of numbers will be between -50 and 50, inclusive.
  • k will be between 1 and 10, inclusive.
  • k will be less than or equal to the number of elements in numbers.
  • maxDist will be between 1 and 50, inclusive.
Examples
0)
{7, 4, 7}
2
1
Returns: 28

The maximal distance is 1, so we can't choose both 7's.

1)
{7, 4, 7}
2
50
Returns: 49

And now it's possible.

2)
{-3, -5, -8, -9, -1, -2}
3
3
Returns: -10

Here, the product will always be negative, so we need to find the product with the smallest absolute value.

3)
{3, 0, -2, 10, 0, 0, 3, -8, 0, 2}
2
2
Returns: 0
4)
{27, 42, 1, 31, -23, 19, 25, -32, 46, -3, -46, 5, -26, 45, 8, -48, -15, -20, 43, 15, 39, -50, 29, 25, -14, -1, -43, 21, 38, 32, -23, 9, 49, 9, -7, 49, 20, -19, 47, -33, 1, 18, 23, -46, 5, -28, 5, 47}
1
7
Returns: 49

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

Coding Area

Language: C++17 · define a public class TheProduct with a public method long long maxProduct(vector<int> numbers, int k, int maxDist) · 84 test cases · 2 s / 256 MB per case

Submitting as anonymous