The Government of Siruseri has decided to auction off land in its oil-rich Navalur province to private contractors to set up oil wells. The entire area that is being auctioned off has been divided up into an M×N rectangular grid of smaller plots.
The Geological Survey of Siruseri has data on the estimated oil reserves in Navalur. This information is published as an M×N grid of non-negative integers, giving the estimated reserves in each of the plots.
In order to prevent a monopoly, the government has ruled that any contractor may bid for only one K×K square block of contiguous plots.
The AoE oil cartel consists of a group of 3 colluding contractors who would like to choose 3 disjoint blocks so as to maximize their total yield.
Suppose that the estimated oil reserves are as described below:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 9 9 9 1 1 1 1 1 1 9 9 9
If K = 2 , the AoE cartel can take over plots with a combined estimated reserve of 100 units, whereas if K = 3 they can take over plots with a combined estimated reserve of 208 units.
AoE has hired you to write a program to help them identify the maximum estimated oil reserves that they can take over.
We can always find a horizontal or vertical line such that one of the three squares is separated from the other two.
--------------------- --------------------- | . -- | | -- -- | | -- . | | | | | | | | | | | | . | | | | | | | | | | | | . -- -- | | -- -- | | -- . | | | |.....................| | . | | | | -- | | . -- | | | | | | . | | | | | | . | | -- | --------------------- ---------------------
We can then separate the two that are on the same side with a second cut. This cut may be parallel or perpendicular to the first cut.
--------------------- --------------------- | . . -- | | -- . -- | | -- . . | | | | | | . | | | | | | . . | | | | | | . | | | | | | . -- . -- | | -- . -- | | -- . | | . | |.....................| | . | | . | | -- | | . -- . | | | | | | . . | | | | | | . . | | -- | --------------------- ---------------------
The first configuration could also occur rotated as two horizontal cuts. The second configuration can occur rotated in three other orientations. So, overall there are six cases to consider.
Case 1
Suppose the cuts are perpendicular.
--------------------- | . | | . | | . | | . | |...........o.........| | (x,y) | | | | | | | ---------------------
Let (x,y) be the point where the cuts meet.
Suppose for every point (x,y), we have computed the following:
Then, for this choice of cuts, the best solution is TL(x,y) + TR(x,y) + BR(0,y).
We can compute TL(x,y) as follows (the others can be done similarly, by rotation).
------------------------------- | . . | | . . | | . . | |.. (u,v) --------- (u,y) | | | | | | | | | | | | | | | | | |.. (x,v) --------- (x,y) | | | -------------------------------
Overall, all these computations can be done in time N^{2}. Remember that there are 3 other rotatational variants of Case 1 to be calculated!
Case 2
Suppose the cuts are parallel:
(0,i+K) -----------o--------- | . . | | . . | | . . | | . . | | . . | | . . | | . . | | . . | | . . | -----o--------------- (M,i)
Without loss of generality, we can assume that the two cuts are at the boundaries of the middle square, so the cuts are at positions i and i+K.
For the left and right rectangles, we can get the best K x K square from the quantities TL(M,i) and BR(0,i+k) that we have already precomputed
What about the best K×K square in the middle strip?
We start with the top K×K square in this strip with bottom right corner (K,i+K) for which we can compute the sum from TLSum as described earlier.
We then walk down this column and keep track of the best K×K square along this strip. Overall this takes time O(N).
In other words, for each i, we compute
This can be done overall in time O(N^{2}). Remember that the horizontal variants of Case 2 must also be calculated!
©IARCS 2012–2016
PÄ›stujeme web | visit: Skluzavky