Sliding Window - Painting The Barn (Gold)

Problems and Contests
#1

I’m having trouble understanding how the external solution manages to find the two rectangles using the subarrays.

More specifically,

  • what do topDP[i], bottomDP[i], leftDP[i], rightDP[i] represent? (for all i)
  • How are these values calculated using the code below?
  • From this, how can we find the two rectangles we need for the answer?

I’ve done my best to understand from the official editorial, but to no avail.
Thanks!!

for (int lhs = 0; lhs <= 200; lhs++)
{
    for (int len = 1; lhs + len <= 200; len++)
    {
        int topSum = 0;
        int leftSum = 0;
        int rightSum = 0;
        int bottomSum = 0;
        for (int i = 1; i <= 200; i++)
        {
            ret = max(ret, topDP[i] = max(topDP[i], topSum = max(0, topSum + rectangleSum(i - 1, lhs, 1, len))));
            ret = max(ret, leftDP[i] = max(leftDP[i], leftSum = max(0, leftSum + rectangleSum(lhs, i - 1, len, 1))));
            ret = max(ret, rightDP[i] = max(rightDP[i], rightSum = max(0, rightSum + rectangleSum(lhs, 200 - i, len, 1))));
            ret = max(ret, bottomDP[i] = max(bottomDP[i], bottomSum = max(0, bottomSum + rectangleSum(200 - i, lhs, 1, len))));
        }
    }
}
for (int i = 2; i <= 200; i++)
{
    topDP[i] = max(topDP[i], topDP[i - 1]);
    leftDP[i] = max(leftDP[i], leftDP[i - 1]);
    rightDP[i] = max(rightDP[i], rightDP[i - 1]);
    bottomDP[i] = max(bottomDP[i], bottomDP[i - 1]);
}

for (int i = 1; i <= 199; i++)
{
    ret = max(ret, topDP[i] + bottomDP[200 - i]);
    ret = max(ret, leftDP[i] + rightDP[200 - i]);
}
#2

First, consider only solving for one rectangle. The code iterates through all pairs of column combinations (lhs, lhs + len), and the rectangle has columns lhs and lhs + len. Then it iterates down the rows, and doing a sliding window to figure out the maximum number of cells that can be painted with K layers for the current rectangle.

For two rectangles, there must exist a line between them (because they don’t overlap). The code contains 4 arrays to simulate the line. For example, topDP[i] means the maximum number of cells that can be painted with a rectangle above row i. Therefore, topDP[i] + bottomDP[i] means that the one rectangle is above i, and one below i.

Hope that answers your questions.

1 Like