×

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) \times (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)$

This question is marked "community wiki".

5★triveni
1.0k1414
accept rate: 12%

19.8k350498541

 0 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. answered 23 Apr '18, 19:39 4★vbt_95 440●6 accept rate: 27% 15.5k●1●20●66 Seems like overkill-imagination for a cakewalk question xD. BTW- fixed editing. (23 Apr '18, 19:53)
 0 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. answered 23 Apr '18, 21:01 4★elli0t 57●4 accept rate: 4%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,688
×41
×20
×6

question asked: 23 Apr '18, 01:02

question was seen: 2,276 times

last updated: 24 Feb, 13:06