After winning a great battle, King Jaguar wants to build a pyramid that will serve both as a monument to remember his victory and as a tomb for the brave soldiers that died in battle. The pyramid will be built in the battlefield and will have a rectangular base of a columns by b rows. Inside it, at ground level, is a smaller, rectangular chamber of c columns by d rows that will contain the corpses and weapons of the fallen soldiers.
The King’s architects have surveyed the battlefield as an m columns by n rows grid and have measured the elevation of each square as an integer.
Both the pyramid and the chamber are to be built covering complete squares of the grid and with their sides parallel to those of the battlefield. The elevation of the squares of the internal chamber must remain unchanged but the remaining terrain of the base of pyramid will be leveled by moving sand from higher squares to lower ones. The final elevation of the base will be the average elevation of all the squares of the base (excluding those of the chamber). The architects are free to locate the internal chamber anywhere within the pyramid as long as they leave a wall at least one square thick surrounding the chamber.
Help the architects pick the best place to locate the pyramid and the internal chamber so that the final elevation of the base is the maximum possible for the sizes given.
The figure shows an example of an 8×5 battlefield with a×b = 5×3 and c×d = 2×1; the number in each square represents the elevation of the terrain in that particular position of the field. The larger marked rectangle the base of the pyramid while the inner marked rectangle squares represent the chamber. This figure illustrates an optimal placement.
-----------------------
1 5 10 | 3 7 1 2 5 |
| -------- |
6 12 4 | 4 3 | 3 1 | 5 |
| -------- |
2 4 3 | 1 6 6 19 8 |
-----------------------
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2
Given the dimensions of the field, the pyramid, and the chamber along with the elevation of every square in the field, find the location of both the pyramid in the field and the chamber inside the pyramid so that the elevation of the base is the maximum possible.
Limits: 3≤m,n≤1000
We can do some preprocessing and compute in MN time for each (i,j) the size of the a×b rectangles and c×d rectangles with top left corner at (i,j).
Now, for each a×b "base" we have to find the smallest c×d "chamber" that we can place within this "base". Since we have to leave a wall at the boundary, we effectively need to find the minimum c×d rectangle within this subrectangle of size (a-2)×(b-2) sitting inside the base. Henceforth, let us denote the size (a-2)×(b-2) as e×f.
Let cd(i,j) denote the size of the c×d rectangle at position (i,j). We want to find the minimum such value in each e×f rectangle in the whole grid. We can do this efficiently in MN time by tiling the whole space as e×f rectangles and computing four quantities for each point inside each tile (see two-dimensional version of min-segment, Session 2, Day 3).
So, overall the problem can be computed in MN time.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky