YPK's blog

When to learn advanced algorithms?
By YPK, 22 months ago, In English

What is appropriate level to learn the following algorithms?

  • Centroid Decomposition
  • Heavy-Light Decomposition
  • FFT
  • Convex Hull trick
  • Persistent Data Structures
  • Treaps
  • Markov Chains
  • Knuth's Optimization
  • Maximum flows
  • Vote: I like it
  • +89
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
22 months ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

Honestly I wouldnt consider max flow as an advanced algorithm since it appears in almost every ICPC contest and all you have to do is to convert the problem to a max flow problem and copy paste your max flow templates. and centroid related problems are basically dfs problems it is really not something that you yourself cant figure out ! however I have never used the decomposition but finding centroid of a tree is used in many interactive problems. the others I have no clue but i read about FFT yesterday and converting problems to fft is much harder than flow problems

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +199 Vote: I do not like it

    I read a blog about topic X for the first time yesterday, and I find it much harder than topic Y which I use regularly for a long time. Nice one.

    Converting problems to flow is much much much harder than converting problems to FFT. FFT is just a fancy way to write convolution. Flow problems just look like NP-hard problems half of the time.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Yes but i dont go for E div1 flow problems man ! The ICPC regional flow problems are pretty easy if you know flow (at least the ones that are solveable for me). I had to learn flow for regional contest

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

      and you are right i did read about FFT yesterday. but even the problems that were listed below it was really hard for me to convert. however when i read flow the sample problems were extremely easy. (like matching etc.) so i was talking about the first impression.

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
        ← Rev. 3   Vote: I like it +46 Vote: I do not like it

        Easy problems are easy. For example, easy dfs problem are easy but try looking for the hard ones that in the end are one (or a few) dfs and you'll be crying about constructionforces for a whole month.

        Ofc the classic flow problems are easy, that's because lots of people know them and they've been repeated a lot in old ICPC contests so it turns into a copy-pasta fiesta. Try a problem like this and without a decent understanding of the theory behind flow stuff you'll run around in circles even though this problem is very straightforward and easy among the "tough" flow problems if you exclude the issue of the author's solution being too slow for strong cases. The hardest flow problems are problems where you model it as flow somehow (in a non-trivial way, for example this) and end up not using any standard flow algorithms because they'd be too slow, usually ending up with some "simulate flow but faster for this specific problem", "find min cut in a smart way" or "use flow to prove that some greedy solution works" solution.

        The middle point would be a flow problem that just requires some non-trivial reduction, as in 101190D. These problems are usually guessable if you are good at guessing.

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

    Thanks!

    → Reply
»
22 months ago, # |
  Vote: I like it +129 Vote: I do not like it

Whenever you feel interested in it.

→ Reply
»
22 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I can't speak to other topics. either I haven't learned them / I haven't practiced them enough / I haven't found any problems on them in the contests I have attempted, however, Flows, FFT and Convex Hull Trick are all fairly easy to understand once you give it some time, and I have seen quite a few problems on them as well.
The hardest part for all three is realising that the problem might be solvable by it and then converting it to a eg. max-flow problem so I suggest learn them and practice a lot.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well...today

→ Reply
»
22 months ago, # |
  Vote: I like it +91 Vote: I do not like it

If you are purple in CF those are appropriate.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

IMHO my CF level could rarely require FFT and Convex Hull Trick. Others are absolutely useless here, on CF.

On the other side, some different (say, ICPC or IOI-styled) contest could require some more provisional algos too. I think I have seen non-learning problems, involving each of the listed topics on some other platforms. So it generally depends on what do you want prepare for.

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

    Thank you. I am not preparing for anything (other than CF).

    → Reply
»
22 months ago, # |
  Vote: I like it +21 Vote: I do not like it

if you are only doing it for codeforces, then learn the topic only after the first time you fail to solve a problem that you reached in a contest because of the topic!

→ Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

For what it's worth, the only topics here I've seen more than a handful of times on CF are FFT and flow. (Markov chains might implicitly come up on a semi-regular basis, but I've never encountered a problem I solved using formal Markov chain methods I've studied as opposed to general intuition.)

I'd argue that everyone Gold+ should have at least a basic familiarity with both FFT and flow. In recent history, these topics have rarely appeared below the ~2500 level, but they're not actually difficult to learn at a basic level: FFT can just be black-boxed (i.e., all you really need to do is find some template code, know that we can multiply polynomials efficiently, and realize that convolutions are often useful in combinatorics problems), and max flow is not especially complicated (and can also be black-boxed if you aren't trying to solve particularly difficult problems). Some basic knowledge of these ideas may be helpful when you end up attempting problems above your level.

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it

    As an aside: it looks like there's some sort of bug in Codeforces' tagging system: typing "~ Gold+" without the space in between tagged a random user in my above comment.

    → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

In case of codeforces its after you become a Master I think, but for other platforms, when you are a stable expert on codeforces because on atcoder E problems are expert level or some times candidate master level problems but I know 600 points problem that use all of those techniques You've written except HLD. Similarly I have seen codechef giving problems on HLD and FFT for 6 star rated contests and DMOJ also start giving you advance concept near 20 points problems or even less. Thing is codeforces keeps the "knowing of advanced concept to solve a problem" to the minimum. So minimum that concepts needed to become expert on codeforces are less than concept needed to crack an average interview (although problems are way harder) but when you go to other sites concept barrier is way higher, so it kinda depends what platforms you give contests on.

→ Reply
»
22 months ago, # |
  Vote: I like it +20 Vote: I do not like it

I know all of them, and haven't used any in a contest. I still don't think its useless to learn them, because they give you more intuition, and its much easier to train understanding difficult things on something concrete and well known like hld, rather than working on a specific hard problem. I think some of these are just genius anyways, and you should learn them regardless of if they really help improve your rating, rating is not the end all be all.

On that note, it doesn't mean I support having more knowledge heavy tasks on codeforces, I think while they're really cool, its not fun to do contests when the bottleneck is how much cp specific tricks do you know.

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

Thanks, everyone for sharing ur experience. I think I've found what I was looking for.

→ Reply