Help on understanding solution of Painting the Barn, Silver 2019

Problems and Contests
#1

Problem: https://usaco.org/index.php?page=viewproblem2&cpid=919
A Solution and Explanation: https://activities.tjhsst.edu/sct/lectures/1819/2019_3_8_February_USACO_Review.pdf
Implementation: Solution - Painting the Barn (USACO Silver 2019 February)

For this solution, -1’s are put at A[x1][y2] and A[x2][y1j]. But does this not kill all of the possible solutions on the row/column that the -1’s are placed, as the line of elements that the corners of the rectangle are connected to are also possible solutions? Shouldn’t these -1’s be placed 1 row and column over?

I feel like I’m missing something big, please help!

#2

I am not 100% sure what you mean by "kill all of the possible solutions on the row/column that the -1’s are placed, but I believe that the issue you are having has to do with the corners being coordinates rather than cells.

A rectangle from (1,1) to (2,2) has area 1, not area 4. As a result, the solution denotes each coordinate to represent the “block of unit area” from (a,b) to (a+1,b+1), and we do not have to place them -1s one row and column over.

1 Like