 #1

Practice

Contest

CAKEWALK

None

Problem:

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?

Explanation:

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) imes (M - 1)

See code below -

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

Image - Insert Image Here

Setter

Tester

Time Complexity:

O(1), per test case.

Space Complexity:

O(1)

#2

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.

#3

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.

#4

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