Hello, codeforces!

All signs in the sky and on the ground indicate that you've enjoyed my first blog, so here is the second one. I've decided to choose a Polish task again, as there are plenty of interesting ones. This time we'll take a look at the "plot purchase" (you can submit here), which is a bit easier, but a few years ago I was very proud of myself when I solved it. The statement goes as follows:

You are given a square n × n grid (1 ≤ n ≤ 2000). In every cell, there is a number from the range [1, 2·10⁹]. You are also given an integer k (1 ≤ k ≤ 10⁹). A task is to find a subrectangle of this grid such that the sum of values in this subrectangle lies in the range [k, 2·k] (or report that there is no such subrectangle). Just print coordinates of its opposite corners.

If the problem would be more difficult, and we'd be asked to find a subrectangle with some given sum of values, then it'd be possible to find it in O(n³) time, just by fixing lower and upper sides and then using two pointers to find for every possible right side the proper left side (if existing). O(n³) is too much, so we have to use the fact that we don't have to achieve the exact sum, which looks really interesting, because many known problems become easier/possible to solve when we change the exact requirement to the range one (knapsack comes to my mind).

Let's firstly look at the sum of all numbers in the grid. If it's smaller than k, then we are sure that there is no proper rectangle (because all numbers in the input are positive). If it already lies in the desired range, then we can end and print the answer. If it's bigger than 2·k, then we need to try a smaller one. Here comes idea which most of the people would go through while solving this problem: let's divide this rectangle into two smaller ones. No matter how, possibly somewhere in the middle, because it looks the most natural (but probably it's a bit easier to implement cutting off rows/columns one by one). Also, the dimension which we'd decrease doesn't matter. After this cut, the sum of numbers in the rectangle with greater sum won't be less than the sum of all numbers divided by 2. So, if the sum was greater than 2·k, then it won't be smaller than k.

Sooo, is it the end? Can we just cut the rectangle as long as it has the sum greater than 2·k and then print what's left? Unfortunately, the answer is no. Let's consider a test case with only one 1 in the corner and 1000 in the rest of the grid. If k is equal to 1, then the only correct answer is to print only this corner. In our algorithm, we could lose it quickly if we'd stay in the wrong half (which is more likely as it has greater sum).

So we need some improvements. Firstly: all cells with values strictly greater than 2·k are definitely forbidden, so we can mark them as infinity. Among all rectangles with no forbidden cells we need to find one with the sum of elements not smaller than k — if we'd have it, then we'll run our algorithm on it. Here we'll again use the fact about only positive numbers: if some rectangle is a subrectangle of some bigger rectangle and the smaller one has sum not smaller than k — then, the bigger one also has such sum. This fact implies that it's enough to look only at rectangles maximal by inclusion, which turns out to be a well know task, but I'll describe it anyway.

We'll need some preprocessing. Firstly, prefix sums for each subrectangle with one corner in cell (1, 1). Secondly, for each cell, we know how far can we go down until we meet either a forbidden cell or an edge of the whole grid.

Let's fix an upper side of the rectangle that we want to find and build an array which indicates how far can we go to the down in each of the columns. Then, if we have some interval of columns corresponding to a rectangle, then it's optimal to go as far to the down as the minimum of values in the array (in this interval). It makes sense, cause it means exatly that when we know left, right and upper side, there is only one reasonable bottom side. Let's iterate over possible right ends of an interval and keep track of places on the left where interval's minimum changes. Why only these places? It's clear that if some interval [i, j] has this same minimum as interval [i - 1, j], then it makes no point to consider [i, j], so we are only interested in intervals whose minimums change after extending that interval to the left (we assume that before and after the array there are values equal to  - ∞). So we can keep these places using a stack. When new value comes, we pop out of the stack values greater than the new one and we consider intervals which start at them and end right before the column in which currently we are. It turns out that the number of considered intervals amortizes to O(n) with a fixed upper side of a rectangle (because we consider something only when we remove it from the stack), so in total there are O(n²) considered rectangles. Complexity is the same, cause when we find any rectangle with the sum not less than k, then we can run our partition-algorithm with the knowledge that for sure it'll find the desired rectangle.

What do you think about this task? Was it interesting or maybe too easy? Let me know what you think about it. See you next time! :D