shoya's blog

Problems which taught you a lot
By shoya, history, 6 years ago, In English

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.

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

»
6 years ago, # |
← Rev. 4   Vote: I like it +22 Vote: I do not like it

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!

→ Reply
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

This blog is my favorite one.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

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!):
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +13 Vote: I do not like it

        Note that the integral trick also has this property — you can establish a lower bound of by looking at the function .

        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

Spoiler
→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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 Graph

Quantity of Strings

Talking about dfs I found the recent question of lyft round pretty interesting too. Intersecting Subtrees

[fixed the links, were not working earlier]

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In recent contests I liked this one - Power tree And its Solution/Proof

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This is indeed a good problem. Thank you for showing it to us.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Airport prom ICPC 2017

→ Reply