Can someone tell me what am I doing wrong?

Problem: https://codeforces.com/contest/22/problem/B

Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) )


10100     //ans is 12


My approach: rectangle with coordinates (x1, y1, x2, y2) is correct if and only if rectangles (x1, y1, x2-1, y2) and (x1, y1, x2, y2-1) are correct, and board[x2][y2] = ‘0’.

ie: dp[x1][y1][x2][y2]=(dp[x1][y1][x2-1][y2] && dp[x1][y1][x2][y2-1] && (board[x2][y2]==0))

If it is correct then find it's perimeter (perimeter = 2*(x2-x1+y2-y1+2)) ie ans=max(ans,perimeter)

And dp[x1][y1][x2][y2]=1 for all i,j when board[x2][y2]==0. Because from point p1 to point p1, ie the same point always have a perimeter is the base case.


Your approach is basically correct. However, be sure to pay attention to a few boundary cases besides the general cases for x2>x1 and y2>y1.

  • Initialize the tables on a single square, i.e., dp[x][y][x][y] = (board[x][y] == 0);

  • Compute the case when the table can be on a single column, dp[x1][y][x2][y] = dp[x1][y][x2-1][y] && (board[x2][y] == 0), where x2>x1.

  • Compute the case when the table can be on a single row, dp[x][y1][x][y2] = dp[x][y1][x][y2-1] && (board[x][y2] == 0), where y2>y1.

For brevity, those boundary cases are not mentioned explicitly in the editorial. Once those cases are included, the algorithm will be fully correct.

  • $\begingroup$ Check my code at Codeforces. $\endgroup$ – John L. Jun 17 '19 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.