Um_nik's blog

Things I don't know
By Um_nik, history, 3 years ago, In English

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 $$$O(n)$$$/$$$O(1)$$$
  • 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 $$$O(n)$$$
  • $$$k$$$-th shortest path
  • Matching in general graph
  • Weighted matching in general graph
  • Preflow-push
  • MCMF in $$$O(poly(V, E))$$$
  • Minimum arborescence (directed MST) in $$$O(E \log V)$$$
  • 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.

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

Comments Comments (190)
| Write comment?
»
3 years ago, # |
  Vote: I like it +138 Vote: I do not like it

Can you also shitpost separately about things only nutella-ish people know pls?

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

Last Line : Destruction Level 100

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

Pretty sure you know what mergesort tree is without knowing that it's called that.

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

    So what is it?

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

      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 $$$[L, R]$$$ then it stores the sorted subsegment $$$[L, R]$$$ of the original array.

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

        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.

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

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

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

          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.

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

          DELETED

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

      Its surprising how GMs don't know merge sort tree. I must be doing something wrong...

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

        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.

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

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

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

arujbansal, how many of these do you know?

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

    Dear ScarletS,

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

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

    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)
    → Reply
»
3 years ago, # |
  Vote: I like it +353 Vote: I do not like it

I believe all these things can be learned from some blog posts or talking with top performers except how Elegia's mind works

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

meanwhile some random chinese 8 yr child : "ha ? These all are well known standard tricks since 1969".

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

Yay, I don't know any of these. See you guys in top 10.

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

Thank you, a lot of contestants get caught up on learning useless (for their level) algorithms instead of using that time to just practice, I'll just send them the link to this blog in the future

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

I don't know any of these :)

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

$$$4\Rightarrow 5$$$

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

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

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

If you only don't know how Elegia mind works, does it mean that you know how everyone else's minds work?

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

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.

Well there might be people who are doing research on some of these topics or doing phd etc. Why you think they have to be red lol.

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

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

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

...And this list is bigger than the list of topics I know!

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

Teach me how to be <red if you know this :D

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

I know most of the things from here. Maybe I am doing it all wrong from the start :"(.

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

    No difference in red and orange

    ask the color blind person

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

oh you are right, but i have to say that many things in this list are well known in china

although they aren't red

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

    So as he said, they are doing them wrong.

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

      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

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

Are you interested in explanations if somebody's sure that his/her understanding is probably the simplest possible?

Also, you don't know how suffix tree works, or how to build it?

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

    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.

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

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

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

      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 $$$O(n^3)$$$ 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.

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

        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 $$$i$$$-th row multiplied by $$$k$$$ to the $$$j$$$-th row, you also need to subtract $$$j$$$-th column multiplied by $$$k$$$ from the $$$i$$$-th column).

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

          Turns out that one LGM was enough.

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

          Do you mean this $$$O(n^3)$$$ algo? Or is there any simpler approach?

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

            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 $$$\mathbb{Q}_{n \times n}$$$)

            And then notice that similarity doesn't change the characteristic polynomial. You need to calculate it for a Hessenberg matrix $$$\mathbf{H}$$$.

            Just use the definition $$$\det(\lambda \mathbf{I} - \mathbf{H})$$$, and use Laplace expansion to recursively calculate the determinant (for every $$$\mathbf{H}_{[1, i] \times [1, i]}$$$).

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

              For commutative rings we may use Berkowitz's method in this paper, which is $$$O(n^4)$$$ but divfree. I don't know is there any $$$O(n^3)$$$ algorithms for commutative rings?

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

              newbies be like how to read this symbol ;)

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

            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 $$$i \times i$$$ block is already in this form and $$$a_{j,k}=0$$$ for $$$j > i, k < i$$$(there can be anything in the $$$i$$$-th column). We need to add $$$i+1$$$-th row and column. Look at values $$$a_{j,i}$$$ for $$$j > i$$$. If they are all zeroes then current block is ended and we start a new one consisting of one cell $$$a_{i+1,i+1}$$$. Otherwise we can move the nonzero element to $$$a_{i+1, i}$$$ by swapping rows(we also have to swap columns with the same numbers, but since we swap rows with numbers $$$> i$$$, we don't care about those columns yet). Then we divide $$$i+1$$$-th row by $$$a_{i+1, i}$$$(and multiply $$$i+1$$$-th column by the same value), so that $$$a_{i+1,i}=1$$$. Then, similarly to Gaussian elimination, we make all other values in the $$$i$$$-th column zeroes by adding $$$i+1$$$-th row multiplied by something(again, we also have to subtract other rows multiplied by the same values from the $$$i+1$$$-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.

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

              Can this be generalized to compute $$$\det(A+Bx)$$$ as a polynomial in $$$x$$$ for arbitrary $$$n\times n$$$ matrices $$$A$$$ and $$$B$$$ in $$$O(n^3)$$$?

              If $$$B$$$ is invertible, we can use $$$\det(A+Bx)=\det(B)\det(B^{-1}A+Ix)$$$

              What about $$$\det(A+Bx+Cx^2)$$$? I only know this can be done in $$$O(n^4)$$$ by evaluating at $$$O(n)$$$ points and interpolating.

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

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

                You can always do elimination on $$$(\mathbf A+\mathbf Bx)$$$ and multiply by $$$x$$$ on a row/column when it has only constants. This progress will stop until $$$\det =0$$$ or $$$\mathbf B = \mathbf I$$$.

                For $$$\det (\mathbf A + \mathbf B x + \mathbf C x^2)$$$, we can do similar elimination to let $$$\mathbf C = \mathbf I$$$.

                Considering a linear recurrent sequence $$$a_n = f_1a_{n-1} + f_2 a_{n-2}$$$. We know that $$$x^2-f_1x-f_2$$$ is the characteristic polynomial of the transition matrix. We try to generalize it when $$$a_n$$$ is a vector, then you will find out that $$$\det(\mathbf I x^2 - \mathbf F_1 x - \mathbf F_2)$$$ equates to the characteristic polynomial of this matrix:

                $$$ \begin{bmatrix} & \mathbf I\\ \mathbf F_2 &\mathbf F_1 \end{bmatrix} $$$
                → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +68 Vote: I do not like it

        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.

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

      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.

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

    https://ibb.co/0McZWgt

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

Dude, I'm not having fun solving problems, I'm having fun learning useless algorithms. Get lost.

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

For what it's worth, I have seen these:

Segment Tree Beats
Link-cut tree
Dominator tree
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
Matroid intersection

in actual contests (although in some cases it was clear that the author just wanted to create a problem using that algorithm). Except for the gf stuff, I copied the code ;) (so you could say I only "know" the generating function ones).

But you are absolutely right, if you are green or blue, the only reason to learn the things in the list above is academic curiosity. They don't come up in problems at that level.

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

    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.

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

    Guilty as charged if you're talking about Grim Treaper

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

      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.

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

But you know math. Thats enough.

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

Request: A list of topics you know.

PS: I didn't know any of these.

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

Ok, but do you know about cheaters?

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

Can you also post about the things you know which is enough to be a LGM -_-??

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

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

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

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +180 Vote: I do not like it
Things I know
Things I can copypaste
Things I don't know

Btw folks, don't be fooled on last sentence. Knowing them is much more important and interesting than stupid internet points.

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

Professor Jelani Nelson (former code jam finalist) talked about this issue in https://youtu.be/7qW8IUZr_K8&t=200 where he noted that most algorithms used in competitive programming are "old" and mostly from before the 1980s.

I would actually love to see a shift in the meta and have more modern algorithms in contests. It's kind of sad that the best minds of our generation are optimized to solve worthless puzzles with binary search instead of pushing the state of the art.

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

    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.

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

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

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

    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 :-(.

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

I know more than 3 but only thanks to geometry :)

But I don't know KMP, Z-function, and finding SCC's in a graph. Or at least I would need to think hard in order to guess/reconstruct the logic.

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

Wow, didn't expect this.

The list just confirms that beginners should focus on general problem-solving techniques rather than these complex (or even intermediate topics).

Problem-solving heuristics that are actually very important, (From Arthur Engel's Problem-Solving Strategies plus additional resources),

  • Invariants
  • Monovariants (increasing/decreasing)
  • Coloring(cycles/modulo)
  • Extremal principle
  • Pigeonhole principle
  • Enumerative Combinatorics, graph theory
  • Number theory
  • Inequalities
  • Induction
  • Sequences, Polynomials, Games
  • Algebra
  • Problem reduction, Identifying subproblems
  • Pattern Observation, trying some examples(Getting your hands dirty)
  • Working Backwards
  • Exchange Arguments
  • Draw a picture
  • Convenient Notation
  • Guessing
  • Symmetry
  • Wishful thinking (What is about the problem that makes it hard?)
  • Penultimate step(What will yield the solution in a single step)
  • Polya's mouse(quickly trying all these techniques above really fast, not getting stuck on one approach)

The first step in most of the competitive programming problems is usually these heuristics rather than the algorithms themselves, which usually reveal themselves after you have progressed using these heuristics above.

ecnerwala also mentioned that in a very difficult problem, there are more than 4 or 5 crucial pieces of information given. The ability to choose what information should be generalized and abstracted out, and which information should not, is important for speed, and it comes only with practice.

Another learning from tourist streams was, he never gets stuck in one approach, and he quickly tries all these approaches in a very short amount of time. I have found it very difficult to even let go of one thought process, once I have gone deep enough. The brain tricks you over and over again not to start from scratch, and you keep retrying that old approach.

Also, if you don't generalize and map those problems to these types of heuristics, every problem will look ad-hoc, and you would not be able to reduce one problem to another.

Resources:

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

I strongly agree with the last sentence, but I can add something like this: Just memorizing algorithms is bad, but getting inspired by them and techniques which are used in them is good.

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

Things you know that no nutella knows: How to get married

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

You are providing a great contribution to the code forces society. Your posts represent great reality the last line reminds me of Bruce lee he told i am scared of a person who practices one move 100000 times I am not scared of a person who knows 100000 moves And "(imagine how many things I haven't even heard of):" reminds me of lord Buddha he said if you consider a big tree leaves as knowledge then I know only 3 leaves Thanks keep posting :p

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

This does not apply to ICPC participants, right?

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

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

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

    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.

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

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

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

uhoh, opps... (in my defense I was red before they moved the cutoff...)

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

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

    — Um_nik to Richard Peng

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

      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.

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

      Opps...

      As soon as this is confirmed to be utterly broken / plausible, I'll go do some remedial dynamic programming... (Section 8 can be viewed as k-nested binary search though)

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

The more you know, the more you know you don't know. $$$\newline$$$ $$$\hspace{80mm}$$$ — Master Oogway (probably)

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

Fortunately, Elegia is red, otherwise he should learn something like how to use binary search sinse he obviously know at least 3 things here.

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

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

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

      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.

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

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

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

I still don't know how to find SCC's, my dumbass just copies Kosajaru's algorithm from cp-algorithms everytime I need it :clown:.

Also don't know any string algorithms (not even KMP) -- hashing has been able to solve almost every string problem I've needed to thus far. Otherwise cp-algorithms it is :)

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

    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.

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

      there are multiple comments here about not SCC, but I think the entire algorithm with proof is only 4 lines which I understood and remembered even when I was blue (needed for a problem).

      1) In condensation graph, there can't be any cycles (cuz then you can get from any component to other in the cycle, contradiction).

      2) Since there are no cycles in the condensation graph, there always exists a component with $$$0$$$ indegree. (cuz in an acyclic directed graph, there always exists such a node).

      3) if there is an edge from component $$$C_{1}$$$ to $$$C_{2}$$$, then $$$tout[C_{1}] > tout[C_{2}]$$$. So let's sort vertices wrt $$$tout$$$

      4) At each stage, we can find a vertex in the "root" component, reverse all edges, and find all the vertices in the root component, remove them, and continue step $$$4$$$.

      That's it, the entire algorithm with proof.

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

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

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

          I mentioned sorting in point 3 (I didn't use the word descending, ok) and tout is so common that I thought I didn't need to define it.

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

            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.

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

              yeah I meant repeat the second line of the step 4, of course. I am not writing a textbook that I need to be so rigorous in my wordings, lol...

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

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

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

I know —

  • Suffix tree
  • 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

I was taught these in a formal course I took. Never used it neither remember them now.

  • Binomial heap
  • Fibonacci heap

I have spent atleast a day reading blogs/watching videos about -

  • Segment Tree Beats
  • RMQ in $$$O(n)/O(1)$$$
  • Any self-balancing tree except treap
  • Link-cut tree
  • Matroid intersection
→ Reply
»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

I believe if you want to learn these stuff, you can learn most of it in less than a month. Given that you have been doing CP for years, spending some time to learn stuff doesn't seem too bad? Then you will possibly not get into the mood for shitpost and feel better!

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

    Inb4 these are the only things he doesn't know among all things he is aware of. The list of thing he knows is probably too long for a blog. :clown:

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

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

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

    Umnik orz

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

If one knows how Elegia's mind works then he will absolutely become red

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

I got motivated by Um_nik ... Do not learn useless algorithms you have never heard of...

(me* thinking every algorithm is useless)... Lets revisit binary search :)

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

So this is how grandmasters flex

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

"Any self-balancing tree except treap". Um_nik Don't you know AVL or Red-Black tree ?

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

How is he even having time to write shitposts after wedding?? Or I am just overthinking? Lol =D

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

I know Li-Chao Tree, Segment Tree Beats, Link-cut tree, a self-balancing tree (Weight Balanced Leafy Tree), Suffix tree, Sweepline Mo, Leftist heap(BTW, the complexity of random heap if (rand() & 1) swap(son[u][0], son[u][1]); is also right)

:) How to solve div.1C?

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

So if someone knows how Elegia's mind works then he/she will absolutely become LGM(?)

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

    Maybe leading to a new color revolution

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

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

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

I know none of these things and I'm doing it wrong,

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

Sweepline Mo

You mean that thing where you process some objects (queries) in some order?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -46 Vote: I do not like it

Message Deleted

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

The topic of this blog should be "_Things I don't want to know_"

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -16 Vote: I do not like it

Not everyone study to become red
UPD- There are some who just likes learning new algorithms. Also read this blog ruban's interview

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

I will learn nothing from this list, yet I will become at least master after 1.5 years.Mark my words.Downvote if you want but I will see you all in this blog after 1.5 years

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

I even don't know what i don't know,how did you come to know what you don't know?

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

PQ-tree sends greetings

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

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

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

I know a bunch of those and I personally believe it's pretty entertaining and brain-developing to learn about it.

Digging papers about max-weight matching in general graphs was the most interesting thing I did during the quarantine of Spring 2020.

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

_< bisecting

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

I'm gonna explain one part of Elegia's derivative magic: $$$\sum_k \prod (k_i!)^{-1}$$$. Anyone should see that with fixed $$$\sum k_i = n$$$ and fixed set of allowed $$$k_i$$$, we're dealing with $$$\prod (\sum_k (k!)^{-1} x^k)$$$, coefficient at $$$x^n$$$.

How do we find $$$f(x) = \sum_k (k!)^{-1} x^k$$$ over all $$$k \ge 0$$$ divisible by $$$d$$$? It looks like the series for $$$e^x$$$, but not quite. We know that $$$e^x$$$ is the only solution of $$$f' = f$$$ with $$$f(0) = 1$$$. Here, $$$f' \neq f$$$, but $$$f^{(d)} = f$$$ since $$$(k^{-1} x^k)' = (k-1)^{-1} x^{k-1}$$$ (except $$$k=0$$$ which disappears).

Now we're solving the linear differential equation $$$f^{(d)} - f = 0$$$. Basic theory says that there must be exactly $$$d$$$ linearly independent solutions in the form $$$e^{\lambda x}$$$, plugging it in gives $$$\lambda^d = 1$$$, i.e. $$$\lambda = e^{2i\pi j / d} = \omega^j$$$ for any $$$0 \le j \lt d$$$. Our function $$$f$$$ is their linear combination $$$\sum_j c_j \mathrm{exp}(\omega^j x)$$$ that satisfies (arbitrary $$$d$$$ initial conditions, we choose nice ones) $$$f(0) = 1$$$ and $$$f^{(1...d-1)}(0) = 0$$$. That gives

$$$f^{(m)}(x) = \sum_j c_j \omega^{jm} \mathrm{exp}(\omega^j x)$$$
$$$\sum_j c_j \omega^{jm} = (m == 0) \quad (0 \le m \lt d)$$$

We can recognise this as the formula for Fourier transform (with usually minus sign for direct, plus for reverse - it's flipped here but it should be obvious to you that it doesn't matter). Reversing it gives $c_j = \frac{1}{d} \sum_m (m == 0) \omega^{-jm} = \frac{1}{d}$. Our function is

$$$f(x) = \frac{1}{d} \sum_{j=0}^{d-1} \mathrm{exp}(\omega^j x)$$$

which can't be further simplified because of $\omega^j$ in exponents.

Now we overload $$$k$$$ and need the $$$n$$$-th coefficient of $$$f^k = d^{-k} \sum \mathrm{exp}((\sum_m \omega^{j_m}) x)$$$ where the outer sum is over $$$0 \le j_0, \ldots, j_{k-1} \lt d$$$.

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

Something thing interesting:

RMQ in $$$O(n)/O(1)$$$

CSP first Round today make problems about it.

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

    In CSP-Senior Group

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

    So sad

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

      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
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        Life really sucks for me...

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

advise from the world champion!

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

I don't know any of those topics, I'm doing it great!

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

What I've known:

  • RMQ in $$$O(n)$$$ / $$$O(1)$$$

  • Mergesort tree

  • Operations on formal power series (Newton method)

  • sweepline

What I'm going to learn:

  • Splay tree

  • Generating functions

  • Link-cut tree

  • Li-Chao sgt

But I cannot even use binary search well...

I am such a loser :(

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

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

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -32 Vote: I do not like it

"Any self-balancing tree except treap" Surprising that a red doesn't know red-black or AVL trees. Should we also know only about treaps?

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

    thx for the advice

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

      Want to add something?

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

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

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

Thanks for the post.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -24 Vote: I do not like it

.

→ Reply
»
2 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Some of my friends know at least 5 of these and can do well on OI contests,but they are only orangy,purple,even blue on Codeforces.They said they are just not used solving problems in a Codeforces contest.Maybe many other players are in the same trouble.

→ Reply
»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I'm doing it wrong:

  • Li-Chao Segment Tree

  • Segment Tree Beats

  • Mergesort tree

  • Splay

  • Link-cut tree

  • Suffix tree

  • Kinetic Tournament

What should I do? wwwwwwww

→ Reply
»
4 months ago, # |
  Vote: I like it -28 Vote: I do not like it

I mean... the whole point is that I'm doing fine without knowing it

truly LGM moment..

don't have to learn anything at all if you already know everything by heart.

this actually reminds me every redcoder is born as redcoder

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

    Doing fine without knowing it... definitely implies that he knows it

    Also realize that copy and paste exists. Solving problems with templates does not mean one knows the algorithm...

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

    That's not the point at all.

    The point is that most of these things are actually really obscure. Most things in that list come up in actual contests like maybe a few times in your entire career.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Imo, the point is that you can learn as many algos as you want, but if your IQ is not high enough, you will never become red. This was implied by the post.

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

        You guys will always find how to twist my words to satisfy your belief that "I'm just not smart enough to be red, God didn't like me, so why even try". Even when I'm literally saying the opposite. Stop learning useless algorithms, go and solve some problems, learn how to use binary search. I mean it.

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it -16 Vote: I do not like it

          Most of these algorithms do actually sound pretty boring, so I'm right there with you.

          Anyway, our point is that a lot of highly-rated users don't truly understand that most people just aren't as capable as them. For example, I see that you're a competitive programming teacher, right? Have you ever successfully trained one of your pupils up to the LGM level? Furthermore, if talent really didn't exist, shouldn't you be able to make all of your highly-motivated pupils LGMs?

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

            you sound like you're stuck at IGM

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it -12 Vote: I do not like it

              Well he believes that talent doesn't exist. If that were the case, everyone should be able to get LGM with the right motivation and practice strategy.

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

                ...and sticking to that practice strategy and spending years practising. You always seem to forget the part where you have to get your ass from the couch and grind problems for hours every day.

                You have 431 problems solved on CF. It is quite decent for a year, good job. I have 4902. And CF never was the main training platform for me. Come back when you have 4902 problems solved. If you are still blue — you win, I will accept that you are just stupid and I am a lucky bastard loved by God.

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

                  Fortunately, I can solve codeforces problems while on the couch. Anyway, I do appreciate the words.

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

                We live in the real world you know. Even my CM, M, and even GM do not necessarily have the "right motivation" to keep pushing. After 2 — 4 years of practicing for several hours per day, they realize that there is much more to life than CP. At some point it becomes unreasonable to continue grinding. There is a sacrifice of time that must be made to practice CP. For many the cost is too great. There is a reason why top competitors started young (less sacrifices needed).

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

                  True. I do not know if you have experienced this, but have you ever done something consistently for 5+ years (a hobby, not a job)? You see so many people come and go. There are only a handful of people who were there when you started and are still there.

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

                I believe such things as "right motivation" and "right practice strategy" are higly situational (as they depend on the indidvidual) and are very difficult to achieve.

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

            Ha, sick burn. Well, how can I measure whether a student is highly-motivated or not? Unfortunately, having a teacher and motivation is not enough by itself. And no, the talent is not the missing part. The missing part is spending thousands of hours honing your craft and getting better.

            I can't know exactly whether my students achieved something (or didn't achieve something) because of me or because of something else. I can be sure though that if they achieved something they did it because they were dedicated to be better. If my contribution exists, it's very small.

            Technically, I'm not even sure they know themselves if I helped them or not. But we can try to ask. Here are some of the people I would consider my students for some time (I'm sorry for the pings):
            - erekle — IOI bronze, silver and gold in consecutive years
            - Ormlis — ICPC World Champion, LGM
            - Siberian, talant and DishonoredRighteous — all reached red for the first time after studying with me. but "after" doesn't mean "because of"
            - Olerinskiy — haven't reached red (yet), but had a huge progress in a short period of time. has a special place in my heart because he actually put me as one of the coaches for an official competition :)

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

              TLDR: Instead of reading this comment, you can just look at the name of the organization on codeforces that I belong to.

              IMHO if anybody with 500 solved problems is not satisfied with the answer like "just solve more problems" and tells something about "talant", "value of knowing algorithms" or some other shit but not hard work, trying to explain something is a waste of time.

              By the way they don't have time to solve problems. But they have time to ask these questions and explain their very important opinion)

              Among the other things Um_nik offered me "just solve more problems".

              I accepted the offer.

              I don't regret it.

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

                How do I start solving problems if I'm lazy? Asking for a friend

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

              In fact, these were the most profitable lessons for me. Um_nik literally passed on the knowledge that comes with a lot of experience. The most important thing is that ideas were studied, not algorithms, and I still use some “do A if you see B in the problem” patterns.

              Regarding the main topic, I think that learning something new and difficult is sometimes fun. After some data structures, I start to think that they are imbalanced in such tasks. But later, you use it maximum once every six months(

              But if you want to increase your rating, solving problems is obviously the most effective way.

              → Reply
»
4 months ago, # |
  Vote: I like it -33 Vote: I do not like it

Maybe you should know them so you may beat Geothermal

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

Almost every Chinese is doing it wrong.

I can just work out problems under 2200(very low in our school's team),but I know at least 5 things in the blog and am learning at least 5 more.Many students in my province will began to learn these things before they're masters.

So I want to ask you,how can I improve faster?Thanks.

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

    Sorry for necroposting. I'm only an IM, but based on my experience, CF doesn't require these very heavy data structures/algorithms (unless of course, you want to solve Div1F during contest). Rather, they require you to be able to make nontrivial observations (easy problems would require you one, harder ones would require multiple) to reduce the problem down to something basic, such as apply greedy algorithm, or a certain DP for a subquadratic complexity, etc. To practice making such observations, the most straightforward way is to solve more recent CF/AtCoder problems (old ones tend to be standard — good for ICPC?) and notice the ideas they use. Upsolving problems using the tutorial also help since it will give you more observation ideas you can use in the future. I know this might have sounded a bit abstract, but again, it worked for me, so hope this made sense! I believe there are many other blogs/comments on this topic, so you can probably search for more insights on this.

    → Reply
»
23 hours ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

I've got:

  • Li-Chao Segment Tree
  • AVL + Splay(Any self-balancing tree except treap)
  • Link-cut tree
  • Leftist heap
  • k-th shortest path
  • Suffix tree

Oh my gosh I have to learn binary search for sure......

→ Reply