arvindr9's blog

By arvindr9, history, 4 years ago, In English

;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.

  • Vote: I like it
  • +56
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by arvindr9 (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

102001A - Edit Distance and 1300D - Aerodynamic have quite nice solution, although I can't prove 2nd one during the contest.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

525D makes you think of complicated stuff with inelegant implementations, but the editorial has a really clever solution that makes this problem way easier.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The observation needed to solve this problem is pretty amazing.

»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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...

the genius observation
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This problem from the recent DMOJ contest is very interesting.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This old codeforces problem (https://codeforces.com/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.com/contest/336/submission/84355595)