pashka's blog

EDU: Two Pointers Method
By pashka, history, 5 weeks ago, In English

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!

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

Comments Comments (37)
»
5 weeks ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

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!

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Ternary Search Please

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Your content is so amazing that this post came as a new year gift to me.

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

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

→ Reply
»
5 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

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

→ Reply
»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

Sqrt Decomposition please

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

finally some gold stuff after a long time

→ Reply
»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

My suggestion would be Number Theory and Combinatorics.

→ Reply
»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Epic !! Next courses suggestion — Tries

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

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

→ Reply
»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Combinatorics, and NOT dp

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Dynamic Programming is still a bottleneck. And the cp part of this topic is yet not covered on youtube.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

combinatorics for next edu lecture please

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please take next topic: Graph, dynamic programming, Number theory!!

→ Reply
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Combinatorial counting theory please.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

DP, Tries

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

string

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

topic suggestion: prefix sum.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Bitmasking dp please

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Dp please.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Dp :D

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can please anybody help me out as I am new to codeforces, my doubt is that in div 2 #698 round i am able to solve only question without any incorrect submission to it, so my rating will increase or decrease? My current rating is 843.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What youtube courses is he talking about ? Can someone please share the link of his youtube courses ?

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

PLEASE DO A COURSE ON COMPUTATIONAL GEOMETRY

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Your dp videos are not available on Twitch can you make them if they are there!!! Thanks

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks for keep adding more lectures.

Suggestions for future topics: MATHEMATICS, DATA STRUCTURES, GRAPH, STRING, GEOMETRY

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very helpful article, I also often use this method. Looking forward to your next articles.

→ Reply