Matrix#400

Matrix (Editorial)

  1. This subtask has restrictions of n,m \le 20. It can be solved in many ways, for example we can iterate over the "centre" of the triangle, iterate through all cells and check whether this cell belongs to the triangle. This gives us \mathcal{O}((nm)^2) time complexity.

  2. This subtask has restrictions of n,m \le 100. Now we could do almost the same, but instead of iterating through all cells and checking afterwards, we could iterate over the cells of the triangle initially. This given us time complexity of \mathcal{O}((n-k)(m-k) k^2).

  3. This subtask has the only additional restriction a_{i,j} \le 1. It differs from others in the way, that we are actually able to replace maximum operations with sum operations — we need to count the number of in the triangle. We can count this sum inside the triangle using prefix sum. First we count prefix sums on rows and then on diagonals. If we had a sum of the previous triangle, we can add a row to it and subtract the sum on diagonal. This gives a time complexity of .

  4. This subtask has restrictions of n,m \le 1000. It can be solved in \mathcal{O}(nm \log^2 k), \mathcal{O}(nm \log k) or in . We are going to discuss solution in \mathcal{O}(nm \log k) here. Important observation: we can split the triangle into three parts — a square of size \lceil \frac{k}{2} \rceil and two triangles of size \lfloor \frac{k}{2} \rfloor. Using this, we need to count the maximum on squares and triangles of \mathcal{O}(\log k) different sizes.

  5. There are no additional restrictions for this subtask. It can be solved in . Let us place "spectators" in every point (\lfloor \frac{k}{2} \rfloor a;\lfloor \frac{k}{2} \rfloor b) for every a,b \in \mathbb{N}. This specators will calculate the blocks of size in each of directions. These blocks have to be calculated in such a way, that if the spectator lies inside the triangle, then we would split the triangle into at most non-intersecting precalculated parts and merge them. To optimize the memory consumption of this solution, we are going to firstly assign a spectator for each triangle, then iterate through specators, precalculate the blocks and then iterate through triangles. This would result in time complexity.