Http://www.usaco.org/index.php?page=viewproblem2&cpid=919

Problems and Contests
#1

http://www.usaco.org/index.php?page=viewproblem2&cpid=919

Can anyone pls tell me how to count the area in this problem? I can use the concept of difference array and prefix sum to calculate the number of coordinates which will have k coats of paint but cannot calculate the area effectively. Couldn’t understand the editorial either.

P.S: This is my first time posting here so pls forgive any mistakes in this post

#2

So the first option is to just bash it out. We can just have an area and increment all the points which have one more layer of paint added onto it. For the sample input,

3 2
1 1 5 5
4 4 7 6
3 3 8 7

We start with the following 2D array.

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

The 2nd line of the input turns it into the following.

1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Continuing on,

1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 1 2 1 0 0 0
0 0 0 1 1 0 0 0 
0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

And finally,

1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 2 2 1 1 0 0
1 1 2 3 2 1 0 0
0 0 1 2 2 1 0 0
0 0 1 2 2 1 0 0
0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0

And after we make the array, we can iterate the entire thing. However, this is \mathcal{O}(n(\text{Max Coordinate})^2). This is way over the time complexity. However, there is a way to get rid of the \text{(Max Coordinate)}^2 using prefix sums. You are given input in the following form,

x1 y1 x2 y2

Now, what if we add 1 to (x_1,y_1) and and (x_2, y_2) while adding -1 to (x_1,y_2) and (x_2,y_1). Then, using the formula for prefix sums on the array, we will get the array we need. I will show this with the sample input. We start off with

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

After the first set of coordinates, we get

1 0 0 0 -1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
-1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

Continuing on,

1 0 0 0 -1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 1 0 -1 0 0
-1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 -1 0 1 0 0
0 0 0 0 0 0 0 0

And finally,

1 0 0 0 -1 0 0 0
0 0 0 0 0 0 0 0
0 0 1 0 0 0 -1 0
0 0 0 1 0 -1 0 0
-1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 -1 0 1 0 0
0 0 -1 0 0 0 1 0

Applying the formula to build the prefix sum array, we get this array,

1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0
1 1 2 2 1 1 0 0
1 1 2 3 2 1 0 0
0 0 1 2 2 1 0 0
0 0 1 2 2 1 0 0
0 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0

And now you can iterate through and find which values are equivalent to K.

#3

when painting area from (1,1) to (5,5) why are we ignoring the 5th row and column? should we not include it in our array so that it becomes
1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
I have done in the same way you showed but took an extra row and column, like added 1 to (x1,y1) and (x2+1,y2+1) and added -1 to (x1,y2+1) and (x2+1,y1). Can you pls tell how we are getting the area when i ignore the last rows and columns? Thanks.

#4

It is because the coordinates given are not for the cell, but coordinates on a grid.