Блог пользователя shoya

Problems which taught you a lot
Автор shoya, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, # |
← 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!

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

This blog is my favorite one.

→ Ответить
»
6 лет назад, # |
← 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!

→ Ответить
»
6 лет назад, # |
← 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!):
→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +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.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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

        → Ответить
»
6 лет назад, # |
← 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.

Spoiler
→ Ответить
»
6 лет назад, # |
← 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 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]

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Airport prom ICPC 2017

→ Ответить