Problems with clever solutions

Правка en4, от arvindr9, 2020-05-03 21:00:50

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.

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.

Теги gcj 1a, #div2d

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)