Things I don't know

I'm just in a mood to shitpost. Don't take it too seriously.

Things that I have heard of, but don't know (imagine how many things I haven't even heard of):

• Li-Chao Segment Tree
• Segment Tree Beats
• RMQ in /
• Any self-balancing tree except treap
• Link-cut tree
• Wavelet tree
• Mergesort tree
• Binomial heap
• Fibonacci heap
• Leftist heap
• Dominator tree
• 3-connected components in
• -th shortest path
• Matching in general graph
• Weighted matching in general graph
• Preflow-push
• MCMF in
• Minimum arborescence (directed MST) in
• Suffix tree
• Online convex hull in 2D
• Convex hull in 3D
• Halfplane intersection
• Voronoi diagram / Delaunay triangulation
• Operation on formal power series (exp, log, sqrt, ...) (I know the general idea of Newton method)
• How to actually use generating functions to solve problems
• Lagrange Inversion formula
• That derivative magic by Elegia
• That new subset convolution derivative magic by Elegia
• How Elegia's mind works
• Sweepline Mo
• Matroid intersection

If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

• 4 months ago, # ^ |

  Wow. It seems like I accidentally "milked a nutella".

• 4 months ago, # ^ |

  So what is it?

  • 4 months ago, # ^ |

    ← Rev. 3 →  

    +32

    It's just like performing merge sort but storing the result of each merge (basically a segment tree) so if a node is responsible for the range then it stores the sorted subsegment of the original array.

    • 4 months ago, # ^ |

      Wow, thanks a lot.

      Btw, does this appear frequently in the problems? If it does, could you please give an example?

      As is known to all, there're lots of trash DS problems in Chinese OJs, including Li-Chao & sgtbeats & LCT & leftist tree... (I've known them even when I was blue, so I'd been wrong for long) but I haven't seemed to meet any problem that uses mergesort tree. I think it's pretty weird.

      • 4 months ago, # ^ |

        I've only seen mergesort tree once in my life. It can be used to solve POJ 2104 K-th Number in per query. chinese article. With fractional cascading the time complexity can be improved to per query. However, it's still not useful because you can solve it with persistent segment tree in time per query and same space complexity.

        • 4 months ago, # ^ |

          Ohhh, got it.

          Thanks :)

      • 4 months ago, # ^ |

        ← Rev. 2 →  

        +19

        I'm not aware of a problem that has merge sort tree as its only solution. Here is a classical problem that you can solve with it.

      • 2 months ago, # ^ |

        ← Rev. 2 →  

        -8

        DELETED

  • 4 months ago, # ^ |

    ← Rev. 2 →  

    -51

    The comment is hidden because of too negative feedback, click here to view it

    • 4 months ago, # ^ |

      ← Rev. 2 →  

      +26

      They just don't know it has a name. It is mentioned in e-maxx segment tree article and in cp-algorithms, of course they know.

      • 4 months ago, # ^ |

        Am I doing something wrong if I know merge sort tree?

• 4 months ago, # ^ |

  Dear ScarletS,

  How dare you insult the almighty arujbansal by thinking that he may not be aware any of these trivial (for him) topics.

  • 4 months ago, # ^ |

    ← Rev. 2 →  

    +29

    Facts. arujorz _/\_

• 4 months ago, # ^ |

  RIP I'm doing it wrong

  • Li-Chao Segment Tree
  • Segment Tree Beats (only range max/min with x updates)
  • Mergesort tree
  • Wavelet tree (just basic construction)

• 4 months ago, # ^ |

  The comment is hidden because of too negative feedback, click here to view it

• 4 months ago, # ^ |

  What happened in 1969??

  • 4 months ago, # ^ |

    Good you aren't asking about 1989.

    • 4 months ago, # ^ |

      What happened in 1989 ?

      • 4 months ago, # ^ |

        ← Rev. 2 →  

        +49

        this comment was deleted by the Chinese government.

        • 4 months ago, # ^ |

          Stop.

      • 4 months ago, # ^ |

        This comment has been removed for violating the state law of one or more countries.

      • 6 hours ago, # ^ |

        Chinese Lost brutally

    • 4 months ago, # ^ |

      <!>DANGER<!>

    • 4 months ago, # ^ |

      The first IOI competition. That's enough.

• 4 months ago, # ^ |

  ← Rev. 2 →  

  0

  You are also Genius OFZ sir.....

• 4 months ago, # ^ |

  For link-cut tree you can use any binary search tree that can split and merge. The complexity will be . I knew some people who wrote link-cut tree with treap, because they were too lazy to learn splay tree.

• 4 months ago, # ^ |

  Obviously it's in the context of learning them for CP, whataboutism sucks.

• 6 hours ago, # ^ |

  No difference in red and orange

  ask the color blind person

• 4 months ago, # ^ |

  So as he said, they are doing them wrong.

  • 29 hours ago, # ^ |

    Actually we're not. In csp-s 2021 's preliminary contest, we test The Method of four Russians ... It's so difficult that I do 0 points in that problem...... And I've seen this dialogue before so I didn't learn it...

    :D :D :D :D

• 4 months ago, # ^ |

  I mean... the whole point is that I'm doing fine without knowing it, but I would be happy to read something well-written, even if I wouldn't understand it.

  Well, I know that suffix tree is a compressed trie of all suffices, and I guess I can build it from either suffix array or suffix automaton, but I don't know the direct way and don't know how to solve problems using it.

  • 4 months ago, # ^ |

    Arguably, just building suffix automaton with suffix links is a very direct way to build suffix tree.

  • 4 months ago, # ^ |

    Yeah, the point is absolutely right, thinking >>> algorithms. I remember when last year, the Polish IOI team was laughing at me for not knowing what Li-Chao tree is.

    Anyway, it's imo interesting that there are huge differences between ways to look at some of these things. I remember when 4.5 years ago I heard from my coach about DMST for the first time, and when I asked how to calculate it, the answer was "oh, it's complicated, some link-cut stuff," and I was like "ohhh, ok, maybe some other time then". This coach was an experienced guy then, and I'm sure that he knew what he was saying. A few years later, I talked with Gennady, and he told me about his way to do this, and it was totally mind-blowing (so I'd be able to implement it during the contest).

    It's similar with HLD. When you first hear about it you might imagine some struct for a segment tree with different sizes and you store this struct for each path, and... ouch. The blog on CF about simply choosing the right way to run pre-order was also mind-blowing for me.

    I know that I'm getting far from your point. Still, maybe it's a nice idea to collect the opinions from the best people on Codeforces and somehow choose which one is the best and create a good guide on "what to think about which algorithm to have the best possible understanding". For example, I'm not exactly sure how to calculate the characteristic polynomial, and quick googling would probably give me some shitty algorithm, but I can bet that after asking 5 different LGMs one of them would have something that almost doesn't differ from the standard Gaussian elimination and can be called a real gold.

    • 4 months ago, # ^ |

      Calculating characteristic polynomial is actually almost the same as Gaussian elimination, but instead of identity matrix you want to get a block-diagonal matrix with blocks that look like this and instead of multiplying by elementary matrices you need to conjugate by them (so for example if you want to add -th row multiplied by to the -th row, you also need to subtract -th column multiplied by from the -th column).

      • 4 months ago, # ^ |

        Turns out that one LGM was enough.

      • 4 months ago, # ^ |

        ← Rev. 2 →  

        +11

        Do you mean this algo? Or is there any simpler approach?

        • 4 months ago, # ^ |

          Another method is to use similarity transformation to transform the original matrix to a Hessenberg matrix, which the process is similar to Gaussian elimination.

          (you cannot always transform it to a triangular matrix, because it doesn't always exist in )

          And then notice that similarity doesn't change the characteristic polynomial. You need to calculate it for a Hessenberg matrix .

          Just use the definition , and use Laplace expansion to recursively calculate the determinant (for every ).

          • 4 months ago, # ^ |

            ← Rev. 2 →  

            +20

            For commutative rings we may use Berkowitz's method in this paper, which is but divfree. I don't know is there any algorithms for commutative rings?

          • 4 months ago, # ^ |

            newbies be like how to read this symbol ;)

        • 4 months ago, # ^ |

          ← Rev. 2 →  

          +5

          I meant to say upper block-triangular instead of block-diagonal. Frobenius form is not needed for characteristic polynomial.

          Just like in Gaussian elimination we assume that upper left block is already in this form and for (there can be anything in the -th column). We need to add -th row and column. Look at values for . If they are all zeroes then current block is ended and we start a new one consisting of one cell . Otherwise we can move the nonzero element to by swapping rows(we also have to swap columns with the same numbers, but since we swap rows with numbers , we don't care about those columns yet). Then we divide -th row by (and multiply -th column by the same value), so that . Then, similarly to Gaussian elimination, we make all other values in the -th column zeroes by adding -th row multiplied by something(again, we also have to subtract other rows multiplied by the same values from the -th column, but we don't care about it yet). That's it, we increased size of the last block by one. Repeat until we transform whole matrix into this form.

          Basically, we do all the same things we do in Gaussian elimination but instead of making diagonal elements into ones or zeroes, we make subdiagonal elements into ones or zeroes. That way when we multiply from the right by the inverse elementary matrix, we don't break anything.

          • 3 months ago, # ^ |

            Can this be generalized to compute as a polynomial in for arbitrary matrices and in ?

            If is invertible, we can use

            What about ? I only know this can be done in by evaluating at points and interpolating.

            • 3 months ago, # ^ |

              Here is an approach after a discussion with zx2003 and mayaohua2003.

              You can always do elimination on and multiply by on a row/column when it has only constants. This progress will stop until or .

              For , we can do similar elimination to let .

              Considering a linear recurrent sequence . We know that is the characteristic polynomial of the transition matrix. We try to generalize it when is a vector, then you will find out that equates to the characteristic polynomial of this matrix:

    • 4 months ago, # ^ |

      I remember when last year, the Polish IOI team was laughing at me for not knowing what Li-Chao tree is.

      You can laugh at them for not knowing what a 3rd place rating in CF is.

  • 4 months ago, # ^ |

    Every time you build suffix automaton and only use the suffix links and not the actual automaton edges in your solution, you solve a problem using suffix tree.

• 4 months ago, # ^ |

  I think I have seen more than half of my list in actual contests. And it is not a list of hardcore nutella stuff, it's just a shitpost from my experience.

• 4 months ago, # ^ |

  Guilty as charged if you're talking about Grim Treaper

  • 4 months ago, # ^ |

    Grim Treaper is not really the same because it's from a problemset meant to teach treaps, as opposed to something like a CF round.

• 4 months ago, # ^ |

  If there would have been a list of algorithms and data structures to learn for becoming LGM, then everyone will be LGM!

• 3 months ago, # ^ |

  ← Rev. 2 →  

  0

  It mainly depends on your logical mind and speed. Some problems only need construction to solve. The algorithms you need won't change much (You can even find a list of algos for NOI in China), and not much new algorithms will come out in a next contest.

• 4 months ago, # ^ |

  I think most problems aren't solved "using" any standard algorithm and for the ones that are, the standard algorithm is a relatively minor part of the problem. The harder and bigger part of the problem is usually the observations beyond the algorithm, that are unique to each problem.

  Old algorithms are used because they solve problems that tend to come up often — like DSU, which comes up in any graph problem. Many new algorithms are much more specialized: it's much harder to use them in a random problem that isn't specifically constructed for this new algorithm.

  There is another class of new algorithms that solve common problems with better asymptotic complexity, which your video talks about a lot. They are not really suitable for us: they usually have a big constant, their implementation is very, very long, or their better complexity is not measurable if the time limit is 2 seconds.

  In short I think what you suggest is an entirely different type of contest.

  • 4 months ago, # ^ |

    In short I think what you suggest is an entirely different type of contest.

    Yea I guess. Our current contest format favors stuff that people can type out quickly which inadvertently limits us to simple stuff. Imagine if we were in a world that didn't have a red black tree in the standard library. Then anything requiring std::set would be treated as the same difficulty as a general BBST because then only people with prewritten libraries can solve them. They will be considered bad or hard problems but in reality we know they aren't that hard to use (or augment).

    So I kind of like the direction atcoder is going with their ACL library. If they start adding more modern algorithms as blackboxes, maybe we will start seeing more problems that can apply them in clever ways. For example we wouldn't even bother talking about "mergesort trees" like it's something interesting if we have a good computational geometry library as a builtin (layered range trees with fractional cascading is 1980s).

• 4 months ago, # ^ |

  ← Rev. 3 →  

  +25

  Personally, I've been constantly amazed how easy it is to print research results that significantly improve the 'state of the art' using competitive programming techniques (mostly segtree & div-conquer, prolly due to my incompetence in other techniques, aka. not being red).

  As a problem setter / contest organizer, I have tried to set problems based on more 'advanced' ideas taught in grad school. Sadly, most of them don't work: oversized cows were very good at finding pre-1980s workarounds to 'modern technology', especially in the blackbox testing + feedback environment. Sadly, unable to convince such people to go print research papers for a few years is one of my greatest failures to date :-(.

• 4 months ago, # ^ |

  KMP and SCCs, what the actual duck XD?

• 4 months ago, # ^ |

  From Where I can access G.M. tourist streams?

• 4 months ago, # ^ |

  Man, he's the only one who got a blog with congratulations on Codeforces. Do you think that no nutella would be able to get married without it?

  • 4 months ago, # ^ |

    The comment is hidden because of too negative feedback, click here to view it

• 4 months ago, # ^ |

  ← Rev. 2 →  

  +33

  Depends on your region. Some regional contests like to spam mindless implementation problems as stoppers, instead of coming up with actual difficult problems.

• 4 months ago, # ^ |

  Speaking as someone that got top2/3 twice in latin america with around 1/2 years of CP experience, it does apply for our region.

  • 4 months ago, # ^ |

    3 years in CP and I still do not reach the top 1 in my country. F

• 4 months ago, # ^ |

  Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

  — Um_nik to Richard Peng

  • 4 months ago, # ^ |

    Yikes, he even knows that I'm terrible at binary search...

    At least he hasn't caught onto the fact that I absolutely cannot do (any interesting) dynamic program, YET.

• 4 months ago, # ^ |

  I'd have taken this advice into consideration if it was LGM Oogway and not Master Oogway.

  • 4 months ago, # ^ |

• 4 months ago, # ^ |

  I am not sure that he knows how his mind works. I certainly don't know how mine works.

  • 4 months ago, # ^ |

    I suggest go TA a course on differential equations (for me it was 18.03), and then think "how many of these homework problems can be turned into coding problems via FFT"....

    I highly suspect whoever wrote those recent ODE based problems had friends taking those classes. At least they haven't started setting using multi-variable PDEs yet.

  • 4 months ago, # ^ |

    He is a Self Aware being, which is why no one can understand his mind.

• 4 months ago, # ^ |

  It is also difficult for me to understand why the algorithm of finding SCC`s is correct. This is one of the few things that I can write without understanding why it works.

  • 4 months ago, # ^ |

    ← Rev. 2 →  

    -47

    The comment is hidden because of too negative feedback, click here to view it

    • 4 months ago, # ^ |

      ← Rev. 2 →  

      +6

      Calling that a proof is too much, you didn't even mention you're sorting in decreasing order and also didn't define tout. After thinking a bit about this I also realized you use Korasaju's algorithm so you also have to understand most people use Tarjan's algorithm because it's way shorter to implement (and there's no need to reverse the graph).

      • 4 months ago, # ^ |

        The comment is hidden because of too negative feedback, click here to view it

        • 4 months ago, # ^ |

          ← Rev. 3 →  

          +3

          Step 4 is also wrong. First of all, you reverse the graph, then you do the rest of step 4, so reversing the edges needs to come before everything else and not be done all the time.

          I think if you called step 4 "Reverse the graph" and step 5 your current step 4 but removing the reverse part then it'd be ok.

          • 4 months ago, # ^ |

            The comment is hidden because of too negative feedback, click here to view it

            • 4 months ago, # ^ |

              It's not a matter of wording. Order matters, things out of order are just wrong.

• 4 months ago, # ^ |

  The comment is hidden because of too negative feedback, click here to view it

  • 4 months ago, # ^ |

    Well, I don't see how that is related to my point...

• 4 months ago, # ^ |

  ← Rev. 2 →  

  -33

  The comment is hidden because of too negative feedback, click here to view it

• 4 months ago, # ^ |

  ← Rev. 2 →  

  +15

  He is already DarkRed

• 4 months ago, # ^ |

  is there a blog about his wedding?

• 4 months ago, # ^ |

  Learn how to use binary search

• 4 months ago, # ^ |

  ← Rev. 2 →  

  -10

  I think you should learn how to use brute force and implementation,and solve div.2B first.

• 4 months ago, # ^ |

  Maybe leading to a new color revolution

  • 4 months ago, # ^ |

    Legendary International Grandmaster (?)

• 4 months ago, # ^ |

  If someone knows how any mind work they will win dozens of Nobel prize for groundbreaking achievement in neurology.

• 4 months ago, # ^ |

  Read the last line of the blog again :)

  • 4 months ago, # ^ |

    Lol its true :-)

• 3 months ago, # ^ |

  Lol, stared. See you in 1.5 years.

• 3 months ago, # ^ |

  sad to see an almost template problem about pq tree appears in the contest as problem I

• 6 weeks ago, # ^ |

  In CSP-Senior Group

  It has 18 points out of 100 points(in total)and I only get 9/18.

  So sad

  • 6 weeks ago, # ^ |

    ← Rev. 2 →  

    +6

    As you see,some problems have low qualities. For example, RMQ in O(n)-O(1), which held 6 points for Cartesian Tree. I bet at least 80% of OIers don't know what's the use of it until yesterday.

    [CensoredCensoredFoundation] is just a pigeon, it knows nothing about setting problems.

    ↑ I'm just in a mood to shitpost. Don't take it too seriously.

    Spoiler

    • 6 weeks ago, # ^ |

      I'm also in ZJ and I probably can not pass the first round...

      Life really sucks for me...

• 2 weeks ago, # ^ |

  You must have learned 四毛子算法 and your "well" is maybe in very high quality.

• 22 hours ago, # ^ |

  thx for the advice

  • 22 hours ago, # ^ |

    Want to add something?

    • 5 hours ago, # ^ |

      I want to. You're completely wrong on several levels. The main points are that you don't need to know maps/sets/other stuff in the C++ STL have red-black/AVL tree underneath, you just need to know the complexity, and that treaps are widely accepted around here to having easier rotations. Maybe you never coded all these trees so you don't know the difference?

      If there's a decent way of modifying STL trees to support some sort of aggregative function (like sum of keys within a range) then please tell me, because rope or whatever it's called isn't decent and someone even made a blog recently reporting about a bug in its implementation (also, it alongside with ordered set and other stuff like this aren't actually in the STL).

• 22 hours ago, # ^ |

  This isn't Facebook