;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.
Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).
Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).
Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).
Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).
Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).
Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).
I think this problem is quite nice. And I do agree with you on the GCJ problem, I was very impressed by how simple it became with that observation!
102001A - Edit Distance and 1300D - Aerodynamic have quite nice solution, although I can't prove 2nd one during the contest.
525D makes you think of complicated stuff with inelegant implementations, but the editorial has a really clever solution that makes this problem way easier.
Just curious — what complicated stuff did you think about?
I thought of a DSU but couldn't implement it, this implementation is close to what I thought.
The observation needed to solve this problem is pretty amazing.
AtCoder is a great source of these, I could go on for days :D
One recent example: AGC 043 C.
Solution: you derive some naive DP to solve the problem in $$$O(N^3)$$$, then...
...you notice that this DP is exactly the same as the "is this state winning" DP for some game and use the theory of Grundy numbers to optimize.
Here is what I thought to solve the problem.
The way bacteria Doubles can be modelled by a binary tree.
The number of nodes in the binary tree is the total current Mass.
In K days you can have 2^K — 1 nodes at max.
Now 2^(K-1) — 1 < N <= 2^K — 1, so I need to delete exactly X number of nodes from my tree and
0 <= X < 2^(K-1)
Write X in binary form, if X =(111..11) in binary then simply delete the entire left subtree of Root.
Otherwise we will Delete a Subtree with 2^B — 1 nodes where B is a bit that is on in X from left subtree of Root, and In the subtree right of Root we will delete a subtree with 1 node for every B that is on in X.
Not sure if you find this approach interesting, thought it was worth sharing.
This problem from the recent DMOJ contest is very interesting.
This old codeforces problem (https://codeforces.net/contest/336/problem/D) fits into that category too. The observations in the editorial trivialize the problem (I had a different solution that finally got AC after a lot of trial and error, which was kind of hard to reason about IMO: https://codeforces.net/contest/336/submission/84355595)