Hyper-minimum

Time limit2sMemory limit256 MB

Summary
Compute the minimum of every M by M by M by M subcube of a 4D array with up to 1.5 million entries.
Level

Medium5 of 10

Topics
Sliding window, Queue
Solved
No attempts yet

Problem

There is a 4-dimensional array XX whose index along every dimension runs from 1 to NN. Build the 4-dimensional array YY defined by

Y[i1,i2,i3,i4]=min⁡X[j1,j2,j3,j4]Y[i_1, i_2, i_3, i_4] = \min X[j_1, j_2, j_3, j_4]

where the minimum is taken over every (j1,j2,j3,j4)(j_1, j_2, j_3, j_4) with 1≤ik≤N−M+11 \le i_k \le N - M + 1 and ik≤jk≤ik+M−1i_k \le j_k \le i_k + M - 1 for each kk. In other words, one element of YY is the minimum of the values inside a 4-dimensional cube of side MM in XX. Every dimension of YY has size N−M+1N - M + 1.

Input

The first line contains NN and MM (1≤M≤N1 \le M \le N). The following lines contain the elements of XX. The number of elements N4N^4 is at most 1500000, and each element is an integer whose absolute value is at most 10910^9. The elements are given in the order that this pseudocode reads them.

for i = 1 to N:
    for j = 1 to N:
        for k = 1 to N:
            for l = 1 to N:
                read X[i, j, k, l]

Output

Print the (N−M+1)4(N - M + 1)^4 elements of YY in the same order as XX, that is, in the order of the same four nested loops. Print all values on one line, separated by single spaces.

Examples4

  1. Example 1

    Input
    1 1
    1
    
    Expected output
    1
    
  2. Example 2

    Input
    3 2
    3 1 4 -4 0 4 0 0 -3 0 -2 -5 5 3 5 -4 4 -3 -5 -4 -4 5 -1 0 -3 -2 -1 2 -5 -5 -1 1 1 -4 3 5 3 -3 -3 3 0 1 4 -1 -2 3 -2 5 4 -1 -5 3 -4 0 -3 -1 3 -1 4 4 -1 -5 -3 4 -4 5 1 5 -4 3 2 2 -2 -2 4 2 -4 -3 1 3 1
    
    Expected output
    -5 -5 -4 -3 -5 -5 -4 -5 -5 -5 -5 -5 -4 -5 -4 -5
    
  3. Example 3

    Input
    2 1
    8 15 9 8 12 17 -8 -9 12 10 20 19 -9 -14 8 -1
    
    Expected output
    8 15 9 8 12 17 -8 -9 12 10 20 19 -9 -14 8 -1
    
  4. Example 4

    Input
    2 2
    7 -3 5 0 2 9 -1 4 6 6 -3 8 1 1 0 -2
    
    Expected output
    -3