Problems with clever solutions

Revision en8, by arvindr9, 2020-05-04 04:43:01

;tldr requesting practice problems with clever solutions (warning: spoilers ahead!)

When I was doing this problem, one of my first observations (and probably many others') was that if $n$ is in the form $2^k - 1$ then you can greedily keep doubling the number of bacteria. Then, I proceeded to finding when I should stop doubling and seeing how many bacteria I should split in the next one or two steps. Finding the last one to two splits was quite inelegant, as can be seen here. This actually took me several hours to get AC (I spent a lot of time doing work on paper to get the inequalities to compute delta correctly).

Then, I read the editorial, and it was much more elegant! It was based on my observation that you can double in the beginning, but rather than adding one to two elements at the end, it adds $n - s$ (where $s$ is the total mass after doubling) such that the list is in sorted order.

I think that one of the reasons I had such a complicated solution was that I might have not had sufficient practice with problems that involve making an observation and making a clever step that makes it trivial.

Another example is the following GCJ 2020 Round 1a problem. I had the observation that each row of the Pascal's triangle has sum $2^k$ but wasn't sure how to get rid of the extra $1$'s when constructing the binary representation -- the editorial gives a clever way to get around this.

Feel free to include practice problems where you can make a clever step to trivialize / simplify the problem in the comments below! Problems of different difficulty levels are welcome.

#### History

Revisions

Rev. Lang. By When Δ Comment
en8 arvindr9 2020-05-04 04:43:01 87
en7 arvindr9 2020-05-03 21:27:16 44 Reverted to en5
en6 arvindr9 2020-05-03 21:25:39 44
en5 arvindr9 2020-05-03 21:03:02 105
en4 arvindr9 2020-05-03 21:00:50 4
en3 arvindr9 2020-05-03 21:00:30 12
en2 arvindr9 2020-05-03 20:59:24 432
en1 arvindr9 2020-05-03 20:59:07 1650 Initial revision (published)