Efficient Sliding Window Minimum with Limited Notebook Storage

Bessie is observing a fast train that passes by twice each day – once in the morning and once in the afternoon. The train consists of $N$ cars numbered from $0$ to $N-1$, and each car $i$ has an integer ID $c_i$. In each pass (morning and afternoon), Bessie sees the cars in order (from $0$ to $N-1$).

Bessie has chosen an integer $K$ and wishes to compute the minimum ID in every contiguous block of $K$ cars, i.e. the minimums for windows $[0,1,\ldots,K-1]$, $[1,2,\ldots,K]$, ..., $[N-K,\ldots,N-1]$. However, Bessie is limited by her notebook which is divided into 5500 cells (numbered $0$ to $5499$), each of which can hold a 32-bit integer (in the range $[-2^{31},2^{31}-1]$). Initially every cell contains the value 0. Also, between successive calls of your main function you cannot retain any additional state except what is stored in the notebook (via the provided functions).

Your task is to help Bessie by implementing an interactive function:

[ void helpBessie(int;ID), ]

which will be called each time a train car passes by (in both passes). When a car passes, its ID is provided as the parameter. You may call the following helper functions in your code:

• int get(int index): retrieves the integer stored in the notebook at the specified index.
• void set(int index, int value): writes the given value into the notebook cell at the specified index.
• void shoutMinimum(int output): outputs a computed minimum for a window. The outputs for the windows must appear in order (i.e. the minimum for window $[0,\ldots,K-1]$ must be output before that for window $[1,\ldots,K]$, etc.). You may output more than one minimum during a single call if needed.
• int getTrainLength(): returns $N$, the total number of train cars.
• int getWindowLength(): returns $K$, the window length.
• int getCurrentCarIndex(): returns the index (between $0$ and $N-1$) of the current car passing by.
• int getCurrentPassIndex(): returns 0 when Bessie is observing the morning train and 1 for the afternoon train.

Because of the limited notebook space and Bessie's inability to retain extra state between calls, you must use the notebook to store all intermediate data. One simple strategy is to use the morning pass to store all car IDs in the notebook and then use the afternoon pass to compute and output the sliding window minimums. Note that since $N$ (and hence $N+1-K$) does not exceed 5500, this approach will fit within the provided notebook space.

Your solution must implement the function helpBessie exactly as described, in an interactive manner. Any correct answer that satisfies the problem will be accepted.

inputFormat

This is an interactive problem. There is no standard input. Instead, the function helpBessie is automatically called with an integer ID corresponding to the ID of the train car that is passing by.

outputFormat

There is no standard output. Instead, use the function shoutMinimum(int output) to output the minimum of each contiguous window of $K$ train cars. The outputs must appear in the same order as the windows appear in the train.

sample

Train Length: N = 5
Window Length: K = 3
Morning Pass: [3, 1, 2, 4, 0]
Afternoon Pass: [3, 1, 2, 4, 0]

Sliding window minimums: [1, 1, 0]