I just finished the Divide and Conquer quiz, and the final question had me beat.

https://brilliant.org/practice/divide-and-conquer/?p=6

The solution suggests looking at a 3x3 grid, then a 7x7 grid, and then generalizes. It wasn't at all clear to me that I ought to be approaching test cases this way, i.e., from a 2^n step standpoint. I started with 4, then went to 5. What were the implicit clues or thought processes that might lead someone to the test cases used in the solution? Or is this just a case of guess and check and I wasn't being precise in my guessing?

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestThe thought process often used in these types of problems, is to work backwards, that is to say, "For what size grid could I answer correctly with only one wrong guess, and clearly that would be going right in the middle of a 3x3 grid. Now, once you have that you can say, OK, with 2 guesses I'd like to get it down to just 3x3 grids, which can be done with four 3x3 grids diagonally adjacent to your guess, which leads to a 7x7 grid, and so on...

Leading eventually to a 2^n type pattern, or in this case for n wrong guesses it would lead to an MxM grid where M = 2^{n+1} - 1.

Make sense?

Log in to reply

Cheers, great explanation.

Log in to reply