All Tracks Data Structures Arrays 1-D Problem

Finding the Subarrays
/

Arrays, Data Structures, One-dimensional

Problem
Editorial
Analytics

You are given an array \(A\) of \(N\) elements. You need to find all the subarrays such that their average sum is greater than the average sum of the remaining array elements. You need to print the start and end index of each subarray in sorted order in a new line.
Notes: 

  • A subarray which starts at  position \(L_1\)and ends at position \(R_1\) comes before a subarray that starts at \(L_2\) and ends at \(R_2\) if \(L_1 \lt L_2\) or if \(L_1 = L_2\) but \(R_1 \le R_2\)
  • The array indexes are in the range \(1\) to \(N\) .
  • The average sum of an empty array is 0.

Input
The first line contains an integer \(N\) that denotes the total number of elements in the array.
The next line contains \(N\) space separated integers that denote the elements of the array \(A\) .

Output
The first line of output should contain an integer \(X\) that denotes how many subarrays that follow the given criterion are there.
The next \(X\) lines contain a pair of space-separated integers corresponding to the start and end positions of the valid subarrays.

Constraints
\(1 \le N \le 2000 \)
\(1 \le A[i] \le 10^6\)

SAMPLE INPUT
3
3 4 2
SAMPLE OUTPUT
3
1 2
1 3
2 2
Explanation

The average of subarray \([1,2]\) is - \((3 + 4) / 2 = 3.5\) , the average of remaining element is \(2/1 = 2\) , thus it is a valid subarray
The average of subarray \([1,3]\) is - \((9) / 3 = 3\) , the average of remaining element is \(0\) , thus it is a valid subarray
The average of subarray \([2,2]\) is - \((4) / 1 = 4\), the average of remaining element is \((3 + 2)/2 = 2.5\) , thus it is a valid subarray

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?