### shoya's blog

By shoya, history, 11 months ago, ,

Hello everyone,
I'm creating this blog post to know about the problems that you once solved and thought to yourself Man I feel amazing after solving this problem. If you remember those favourite problems or you know some problems which requires amazing concepts to learn and you were in awe of the beauty of the problem then post their link in the comments and share them with us.The problem need not be necessarily from codeforces it could be from any judge.

• +30

 » 11 months ago, # | ← Rev. 4 →   +22 A few months ago I have come across with this Power Tower problem and I was fascinated by the problem and then learnt a cool trick.You can check out the problem if you want!
 » 11 months ago, # |   +28 This blog is my favorite one.
 » 11 months ago, # | ← Rev. 2 →   +7 One of the most beautiful things that ever happened to me in CP is Factoradic Number!Using this you can find k-th lexicographically smallest permutation of size n and vice versa in O(nlogn)You can apply this cool trick in this Misha and Permutations Summation problem.Happy Coding!
 » 11 months ago, # | ← Rev. 2 →   +34 This is a well-known trick but I first discovered it when solving Zebra from Olympiad of Metropolises 2016. The trick (not the full solution though!):.Proof (in the terrible figure below, n = 20) The sum is simply the area covered by the purple boxes. To give an upper bound, we can calculate the area under the green curve, which is piecewise defined as f(x) = 1 for x < 1 and for x ≥ 1. This area is, naturally:.Therefore,.How does this help in solving problems? This gives some algorithms unexpectedly good complexities. For example, suppose you have an array with length n and then you: divide the array into 1 block and do something with complexity in each block; divide the array into 2 blocks and do something with complexity in each block; divide the array into 3 blocks and do something with complexity in each block; ... divide the array into n blocks and do something with complexity in each block. The total complexity is, magically, !
•  » » 11 months ago, # ^ |   +42 Here's another fun way to get the approximation by grouping powers of 2 terms: times 1 Also here you can find an application of this in an expectation problem.
•  » » » 11 months ago, # ^ |   +11 A nice feature of this trick is that you can similarly group the terms of powers of 2 in a different way: , so in fact the sum is and is thus , so this is a totally accurate runtime order, not just an upper bound.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +13 Note that the integral trick also has this property — you can establish a lower bound of by looking at the function .
 » 11 months ago, # | ← Rev. 2 →   +5 I liked USACO Censoring (Gold) because I came up with the solution myself (I thought it was quite clever) This is a somewhat well known idea, but I didn't know about it before I came up with it. SpoilerThere can only be up to sqrt(N) distinct string sizes
 » 11 months ago, # | ← Rev. 3 →   +5 When I was learning about dfs, I found 2 very simple questions which can be solved just by dfs and doesn't require any complex idea, just understanding the question and a simple required thought . I found those 2 problems to be quite interesting, even though it might not teach you a lot.Cycle in GraphQuantity of StringsTalking about dfs I found the recent question of lyft round pretty interesting too. Intersecting Subtrees[fixed the links, were not working earlier]
 » 11 months ago, # |   +3 In recent contests I liked this one - Power tree And its Solution/Proof
•  » » 11 months ago, # ^ |   +3 This is indeed a good problem. Thank you for showing it to us.
 » 11 months ago, # |   0