smax's blog

[Tutorial] Divide and Conquer
By smax, 3 years ago, In English

Hey everyone,

I recently started a blog, and I think one of my articles on divide and conquer turned out pretty well, so I thought I'd share it here: https://mzhang2021.github.io/cp-blog/divide-and-conquer/. It covers both common and rarer techniques.

Speaking of the blog, if you're interested feel free to check it out here. I plan on posting regularly, and you can find more information in my introductory post.

Why not just post blogs on Codeforces? Why make a separate blog?

Thank you!

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

Comments Comments (10)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

After reading your TC argument for "BinarySearch's : Every Sublist Containing Unique Element". I was confused how min(a, b) changes overall TC from O(N^2) to O(NlogN).

This helps a lot in learning that. Xiaowuc1 Solution

And definitely this optimisation is non-trivial to think about.

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

    It's funny, I actually read that same explanation but didn't quite understand how he went from $$$ \mathcal O(n^2)$$$ to $$$\mathcal O(n \log n)$$$ with the $$$\min(a, b)$$$ optimization, which is why I came up with the "small-to-large" explanation. But yeah, I agree this is a non-trivial change in complexity to think about, and I'd be willing to edit the part of the explanation that you found confusing.

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

      The TC Notation :

      k is the location of unique element.

      Without optimisation looks like T(n) = T(k) + T(n - k) + O(n).

      After this min(a, b) optimisation it becomes : T(n) = T(k) + T(n - k) + O(min(k, n - k)).

      I particularly didn't get how you correlated this with small-large-merging. I know that the worst-case will occur when unique element is found in the middle at every level of our recursive tree. Can you explain more ?

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

        Ah, so I reread that section of the article and I guess it is a bit terse. Basically, I refer back to the analogy of graphs (treating each state representing the range $$$[l, r]$$$ as a component of nodes $$$l, l + 1, \dots, r$$$) used in the previous section about the CF problem. So this particular paragraph:

        Paragraph

        Now based on this analogy, I refer to the recursive tree. Each state that splits into two child state can be thought of in reverse: two child states merge to become one state. In small-to-large merging, when we merge two components of size $$$a$$$ and $$$b$$$, we only iterate over the nodes in the smaller of the two components, so its $$$\mathcal O(min(a, b))$$$ work. That's essentially the same thing we're doing here: we only do $$$\mathcal O(min(a, b))$$$ work since we only iterate as much as twice the size of the smaller subproblem in our divide and conquer (twice since we iterate on both ends).

        I'll see if I can rephrase that paragraph in the article to make it more clear, thanks!

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

          Ah, I see.

          Please explain this line as well : And so by the same analysis as small-to-large merging, our runtime is O(nlogn).

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

            I've updated that section of the article if you want to check it out (you may have to hard refresh cause caching).

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

Congrats on hitting red!

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

Nice blog! By the way, why didn't you use the term disjoint sparse table in CodeChef SEGPROD?

Another note is that Old Messy Code Written 4 Months Ago seemed to me much more clear that the explanation) I was confused by the following case and the code helped me.

P. S. How can I insert a picture, so that it isn't stretched to the width of the comment? The picture above consists of the table and extra white space to the right.

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

    Thanks for reading! I didn't know "disjoint sparse table" was common terminology for the trick used in SEGPROD.

    For "Find the Path," I just looked at the case you posted and realized I didn't actually explain the algorithm correctly in text (although it's correct in code). The optimal solution is actually computed in the root state solve(0, 7) and uses two paths stemming from the middle column with index 3 and contained between columns 0 and 7, while the explanation suggests that a query $$$(ql, qr)$$$ can only get its optimal answer from two paths stemming from some column $$$ql \leq m \leq qr$$$ and not leaving columns $$$[l, r]$$$. I'll update the article to fix that. EDIT: The article has been updated.

    For the image I think you can just crop your image file before uploading.

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

      If I crop the picture, it becomes greater and loses quality. However, the picture below looks somehow fine though the original is smaller.

      → Reply