Connection Status:
Competition Arena > ContiguousSubsequences

ContiguousSubsequences

SRM 382 · 2007-12-11 · by dkorduban

SRM 382 · 2007-12-11 · by dkorduban · Simple Search, Iteration
Class Name: ContiguousSubsequences
Return Type: int[]
Method Name: findMaxAverage
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

Given an integer sequence a[0], a[1], ..., a[N-1], find a contiguous subsequnce a[i], a[i+1], ..., a[j] such that:

  1. The length of the subsequence (j-i+1) is at least K.
  2. The average value in the subsequence (a[i] + a[i+1] + ... + a[j])/(j-i+1) is maximized.

You are given a int[] a containing the original sequence, and an int K. Return a int[] containing exactly two elements. The first element is the first index of the contiguous subsequence described above, and the second element is the last index. Both indices are 0-based. If there are multiple subsequences that satisfy the conditions above, return the longest one among them. If there are still multiple subsequences, return the one among them with the smallest first index.

Constraints

  • a will contain between 1 and 50 elements, inclusive.
  • Each element of a will be between 0 and 1000000, inclusive.
  • K will be between 1 and number of elements in a, inclusive.
Examples
0)
{1,3,7}
2
Returns: {1, 2 }

There are 3 possible contiguous subsequences: {1,3}, average = 2. {1,3,7}, average = 11/3. {3,7}, average = 5. So {3,7} is the best case.

1)
{5,1,3,4}
2
Returns: {2, 3 }
2)
{10}
1
Returns: {0, 0 }

There is only one possible subsequence - the whole sequence.

3)
{381,921,513,492,135,802,91,519}
1
Returns: {1, 1 }

When K = 1, we can select the subsequence containing only the maximal elements.

4)
{381,921,513,492,135,802,91,519}
4
Returns: {0, 3 }
5)
{1,1,1,0,0,1,1,1}
4
Returns: {0, 7 }

counterexample for greedy

6)
{0,0,0,0,0}
1
Returns: {0, 4 }

all zeros

9)
{10,3,4,5,10}
1
Returns: {0, 0 }

two maximums

10)
{1,9,10,3,4,6,9,10}
2
Returns: {1, 2 }

two maximums

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

Coding Area

Language: C++17 · define a public class ContiguousSubsequences with a public method vector<int> findMaxAverage(vector<int> a, int K) · 111 test cases · 2 s / 256 MB per case

Submitting as anonymous