GlobalWarmingCheck | Topcoder Archive

Problem Statement

We are recording temperature at regular intervals. You are given a log of last N recorded temperatures: values T[0] to T[N-1]. Value T[0] is the earliest measurement, value T[N-1] is the most recent one.

In this problem, we will use the following values: T[i] = (i*i + 4*i + 7) modulo M. As usual, a higher value is warmer.

Each group of Y consecutive measurements represents a time interval of one year.

You would like to verify whether global warming is happening during the time that corresponds to your measurements. To do this, you need to find the year-long interval with the coldest average (the first such interval, if there are ties) and the year-long interval with the hottest average (the last such interval, if there are ties).

More formally, we are looking at all contiguous segments of length Y in the given sequence of measurements. Among them, find

The smallest index lo such that the average of the values T[lo], ..., T[lo+Y-1] is minimal.
The largest index hi such that the average of the values T[hi], ..., T[hi+Y-1] is maximal.

Return {lo, hi}.

That is, return a int[] with two elements: element 0 should be lo and element 1 should be hi.

Definition

Class:: GlobalWarmingCheck
Method:: solve
Parameters:: int, int, int
Returns:: int[]
Method signature:: int[] solve(int N, int M, int Y)
(be sure your method is public)

Constraints

N will be between 1 and 1,000,000, inclusive.
M will be between 1 and 1,000, inclusive.
Y will be between 1 and N, inclusive.

Examples

```
12
```
```
20
```
```
1
```
```
Returns: {8, 4 }
```
The sequence of temperatures is T = {7, 12, 19, 8, 19, 12, 7, 4, 3, 4, 7, 12}. As Y=1, we are looking at segments that consist of a single measurement. The average temperature in a one-value segment is simply that value, so we are looking for the leftmost minimum and the rightmost maximum in the array.
```
12
```
```
20
```
```
4
```
```
Returns: {6, 2 }
```
The temperatures are the same as in the previous example. The segments T[6], T[7], T[8], T[9] and T[7], T[8], T[9], T[10] both have the smallest average temperature of 4.50. The segments T[1], T[2], T[3], T[4] and T[2], T[3], T[4], T[5] both have the largest average temperature of 14.50.
```
12
```
```
1
```
```
3
```
```
Returns: {0, 9 }
```
All segments have the same average temperature of 0, so we simply want the leftmost and the rightmost of them. Note that the rightmost segment starts at index 9. It contains the values T[9], T[10] and T[11].
```
57000
```
```
997
```
```
23
```
```
Returns: {984, 56322 }
```
Watch out for integer overflow when computing the values T[i]. In particular, the value i*i does not always fit into a 32-bit integer.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.