## Editorial for IOI '06 P2 - Pyramid

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

SOLUTION 1: For every possible position of the pyramid, add up the heights of all the squares in the pyramid base; after that for every possible position of the chamber within that pyramid, subtract the heights of the squares in the chamber to the number obtained for the pyramid base. Keep in memory the maximum height for that position of the pyramid and proceed to the next possible position. This algorithm has a running time of and should score at most 30 points.

SOLUTION 2: Instead of recalculating the sum of the heights for each possible position of the pyramid within the field, or the chamber within the pyramid, use the previous result. That is, calculate the first position, after that in order to move, for example, to the left, just add the new column of squares and subtract the rightmost one. This can be optimized by precomputing the sum of all the rectangles of size and of size in time and storing them into an array. This algorithm has a running time of and should score between 50 and 59 points depending on how good is the implementation.

SOLUTION 3: Precompute the sum of all rectangles of size and of size as described in solution 2. For each row and for each column in the grid create a binary tree that allows you to search for the smallest number within any interval in time log time, populate these trees with the values of the rectangles of size . Instead of checking every possible position of the chamber within the pyramid, use the binary trees to search for the minimum value of the chambers within the desired range. This algorithm has a running time of . If efficiently coded this algorithm scored 100 points.

OPTIMAL SOLUTION: Precompute the sum of all rectangles of size and of size . Now we need a way to find the minimums for each row and column in linear time. Suppose that , that is, the number of different columns where the chamber can start within a given pyramid is . That means that for every group of consecutive rectangles of size in a row, we have to find the minimum among them to know which is the best position to locate a chamber within that row. Look at the following figure:

The first line contains the sums of the rectangles of size for some row.

The second line contains a vector of length that was constructed growing from right to left taking the minimum value between the corresponding position in the first line and the previous value in the vector.

The third line is a vector constructed like that of the second line but growing from left to right.

Finally, the position of the fourth line contains the minimum value of every group of eight consecutive squares starting at position . To compute each minimum take the minimum value of the position of the vector in the second line and the position of the vector in the third line.

Constructing these vectors for each row and column will give you the minimum value of every possible chamber in time thus resulting in an algorithm with running time .