← All solutions

Writeup by Onufry

Shortest judge solution: 1443 bytes. Shortest team solution (during contest): 1224 bytes.

This proved to be one of the tougher problems in the competition. The most naive solution to this problem would take Ω(n⁶ ) time. With very little effort, this can be improved to a Θ(n⁴ ) solution, but this is still too slow. Fortunately, yet another factor of n can be shaved off in the running time.

It is instructive to first consider a 1-dimensional variant of the problem. Given an array x₀ , . . . , x_n−1 , and a subsequence [ j, k) of it (that is, x_j , . . . , x_k−1 ), we are interested in the values V (k, j) := (k − j) · min_j≤i<k x_i . In particular, we are interested in sequences that maximize this value.

Consider a subsequence [k, j), assume that x_i is the minimal value of the elements of this subsequence. If V (k, j) is a candidate to be the largest value, this means x_k−1 < x_i and x_j < x_i — otherwise we could extend the interval to get a higher V value. So now, for each i, we will calculate the longest subsequence that has its minimum at x_i .

To do this, we will do a single run through the x_i sequence and a use stack. We will go through the sequence, and for each element x_i we will first pop all elements that are larger or equal to it from the stack, and then push x_i onto the stack. This way, the elements on the stack will always be in increasing order (since we never add an element that’s smaller or equal to the one before it). When we pop an element x_i from the stack, we can actually calculate the longest segment with the minimum at x_i . Since we’re popping x_i , the element we’re inserting (call it x_k ) is necessarily smaller than x_i ; and since we didn’t pop it so far, x_k is the first element smaller than x_i . Similarly, the element directly preceding x_i in the stack (call it x_j ) has to be the last element smaller than x_i — if there was something between them, it wouldn’t have been popped. Thus, when we pop x_i from the stack, we can add x_i · (k − j − 1) as a candidate for the largest V (k, j) value. Thus, in O(n) time, we can get all candidate values for the largest V (k, j).

Now to solving the full problem. For a fixed column c, and each 1 ≤ r, t ≤ m, we can calculate min_r≤s<t x_c,s in O(m² ) time, in a number of ways (like DP, incrementally increasing interval length). Let’s do it for all columns, in O(m² n).

Now, fix the vertical dimension of the chest d, and fix the top row z in which the chest begins. Then we are interested in the highest value of d · (k − j) · min_z≤s<z+d min_j≤i<k x_i,s . We have already precalculated what the lowest value of x_i,s is for any fixed i over z ≤ s < z + d, let’s call it m(i ) (it depends on z and d as well, but we’re treating these as fixed). So, we’re interested in d · (k − j) · min_z≤s<z+d m(i ) — but this is exactly the one-dimensional problem we know how to solve in linear time! Thus, we solve it for all z and d values, and obtain an O(mn max(m, n)) algorithm for the whole problem.