CUTBOARD - Editorial

Problem Link:



Setter: Alei Reyes

Tester: Triveni Mahatha

Editorialist: Triveni Mahatha






Given N x M chessboard. Make cuts on some of the edges but don’t cut the board into pieces. How many maximum such cuts can you make?


Note that we can make cuts between every two consecutive row of cells. There will be N - 1. Such rows to be cut. Within a row we can make M - 1 cuts. This way of cutting will make the board look like an extended E - shape structure. Refer to the figure for more understanding -

So number of cuts is (N - 1) \times (M - 1)

See code below -

    int T = readInt();
    while(T --> 0) {
       int n = readInt();
       int m = readInt();
       int ans = (n - 1) * (m - 1);

Image - Insert Image Here




Time Complexity:

O(1), per test case.

Space Complexity:


Imagine it as a graph with N*M nodes. In each row we have M-1 edges. Similarly in each column we have N-1 edges. Total we have N*(M-1)+M*(N-1) edges. And we have to make a spanning tree from this graph which which will have total edges equal to it’s number of nodes-1 which is N*M-1 edges.
Difference is N*(M-1)+M*(N-1)-(N*M-1)
which finally evaluates to same expression (N-1)*(M-1) as above.

Seems like overkill-imagination for a cakewalk question xD. BTW- fixed editing.

I think too many example cases were given in this question. One can easily solve the question without even reading it and looking on the test cases. I did not read the question carefully and found the pattern by examining the example cases. Tried it and got AC-ed.