Hyper-minimum
Time limit2sMemory limit256 MB
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 whose index along every dimension runs from 1 to . Build the 4-dimensional array defined by
where the minimum is taken over every with and for each . In other words, one element of is the minimum of the values inside a 4-dimensional cube of side in . Every dimension of has size .
Input
The first line contains and (). The following lines contain the elements of . The number of elements is at most 1500000, and each element is an integer whose absolute value is at most . 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 elements of in the same order as , that is, in the order of the same four nested loops. Print all values on one line, separated by single spaces.