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

Автор pashka, история, 4 года назад, По-английски

Hello Codeforces!

It's been a long time since I posted a lesson in EDU section. Sorry about that, was quite busy managing my course on Youtube.

New lesson is about two pointers method.

Go to EDU →

What topics you want to learn next? I would prefer topics not covered in my Youtube course, something more specific for competetive programming. Any ideas?

More about EDU section you can read in this post.

Thanks to Stepavly and Supermagzzz for their help with lecture notes and testing problems.

Enjoy the lesson and good luck on the contests!

  • Проголосовать: нравится
  • +553
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

This is epic!

Suggestions for future topics: Tries, Ternary search, Trees

Also I noticed that this lesson and this lesson are only available in Russian. It would be good if they can be translated into English so more people can learn. Thanks!

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

Ternary Search Please

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hi! Ternary search is not much important if you know binary search. Ternary search problems can also be solved using binary search. In binary search you will go the mid element and check for the previous and next element and based on your check condition you can either go to left or right.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can't do that if the values can be non-integer.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I am just asking in curiosity. Even if the values are non-integer, and the error allowed in the problem is 'delta' (let which is generally 1e-6). Then can't we check for mid+delta and mid-delta and then eliminate half part according to the check condition.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          You just explained terrnary search, the only difference is that usually in terrnary search the values you mentioned (mid-delta, mid+delta) are selected in a way that they divide the range into 3 equal parts (that's why it's ternary), which makes the code better and less likely to fail because of precision errors.

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

Thanks for this. Suggestions : Graphs topics like Trees, DP on Trees, etc.

»
4 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

FFT please! By the way, i appreciate your work.

»
4 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Sqrt Decomposition please

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I am not sure but do we need it when we have segtrees?

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

      i guess there are some differences on memory usage and time complexity witch makes it better than segtree in some cases.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, of course. Square root decomposition can handle some types of queries that segment tree can't (or at least it isn't clear that you can handle them).

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

My suggestion would be Number Theory and Combinatorics.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Epic !! Next courses suggestion — Tries

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

what about SCC and topological sort, or 2-sat?

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Combinatorics, and NOT dp

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Combinatorial counting theory please.

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

string

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

Your content is great and very easy to understand! I think more lectures in some hard DP topics (e.g. DP knapsack on Tree, DP on Trie, DP Sum over subsets) or maybe some problems that are a combination of simpler algorithms (like, greedy + DAG, bitmask + shortest paths ...) would be very helpful for a lot of people that know all of the basics, yet struggling to apply them into actual problems.

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

PLEASE DO A COURSE ON COMPUTATIONAL GEOMETRY