USACO Gold Painting the Barn

[joshualiu555]

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

The sample test case doesn’t seem to make sense (It does, I just can’t see it)

This is the array that shows the coats of paint for each cell.
1 1 1 0 0 0
1 2 2 1 1 1
1 2 3 2 2 1
0 1 2 2 2 1
0 1 2 2 2 1
0 1 2 2 2 1
0 1 1 1 1 1

This is the conversion to a 1 -1 array.
1 1 1 0 0 0
1 -1 -1 1 1 1
1 -1 0 -1 -1 1
0 1 -1 -1 -1 1
0 1 -1 -1 -1 1
0 1 -1 -1 -1 1
0 1 1 1 1 1

The ideal solution seems to be to keep all the -1’s, which adds up to 14. Then paint the right most column 2 left most columns, which adds up to 10. However, this only adds up to 24 while the answer is 26.

The only thing I can really think of is that the two -1’s I covered painting the left side didn’t count? (Sorry if that doesn’t make sense)

Is there a more ideal solution or am I misunderstanding? Any help would be greatly appreciated

[pavanscoding]

Problem statement confusion (2019 Feb Gold)

In the problem Painting the Barn, the sample test cases produce the following (truncated) grid (number in the cell represents the number of coats of paint applied): [image] Now, we can paint regions (2,7)\rarr (8,7) and (8,2)\rarr (8,6) to give a total of 33 cells with 2 coats of paint. However, the answer states 26. What is the mistake in my diagram or notation?

The points given aren’t cells, but coordinates.

[joshualiu555]

I don’t think that’s the issue. I was always using the coordinates as corners.

[pavanscoding]

I don’t think so because the box around (1,1)\rightarrow (4,4) should be a 3\times 3 square.