PROBLEM LINKS
DIFFICULTY
Easy
PROBLEM
The problem is very simple. We are given a NxN grid, with dots at the intersecting points, and we have to find the maximum number of lines we can draw connecting two diagonal dots, starting from position (0,N-1) without a break, i.e. without picking up the pen while drawing
EXPLANATION
This problem has two cases, N is even or odd. If N is even, we first draw a diagonal line from (0,N-1) to (1,N-2). Then from (1,N-2) to (2,N-1) and so in in this criss-cross way. If we continue this way we will end up at (N-1,N-2). From this point we move up in the grid just the same criss-cross way that we have come down. So, we draw the line (N-1,N-2) to (N-2,N-3) and then keep moving up. In this way we fill out the whole grid. So in a completely maximum filled grid, there are (N-1) diagonal lines vertically and N-1 lines horizontally. So maximum possible lines are - (N-1)(N-1).
The approach is the same when N is odd, but while drawing diagonal lines coming down vertically, we cannot go to the lowermost row, as we will end up at (N-1,N-1) dot and being the right-bottom dot, that will be the last dot we can draw to. Hence to avoid that, we have to start goig upwards from the N-2th row itself. So in a completely maximum filled grid with odd rows and columns, there are N-2 lines vertically and N-1 lines horizontally. So maximim possible lines are - (N-2)(N-1)
AUTHOR’S SOLUTION
Author’s solution can be found here