Um_nik's blog

By Um_nik, history, 11 months ago,

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

• +1965

 » 11 months ago, # |   +138 Can you also shitpost separately about things only nutella-ish people know pls?
•  » » 11 months ago, # ^ |   +25 Wow. It seems like I accidentally "milked a nutella".
 » 11 months ago, # |   +150 Last Line : Destruction Level 100
 » 11 months ago, # |   +329 Pretty sure you know what mergesort tree is without knowing that it's called that.
•  » » 11 months ago, # ^ |   +7 So what is it?
•  » » » 11 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 $[L, R]$ then it stores the sorted subsegment $[L, R]$ of the original array.
•  » » » » 11 months ago, # ^ |   0 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.
•  » » » » » 11 months ago, # ^ |   +32 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.
•  » » » » » » 11 months ago, # ^ |   0 Ohhh, got it.Thanks :)
•  » » » » » 11 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.
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   -8 DELETED
•  » » » 11 months ago, # ^ | ← Rev. 2 →   -51 Its surprising how GMs don't know merge sort tree. I must be doing something wrong...
•  » » » » 11 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.
•  » » » » » 11 months ago, # ^ |   -19 Am I doing something wrong if I know merge sort tree?
•  » » » » » » 9 months ago, # ^ |   0 nope
 » 11 months ago, # |   +100 arujbansal, how many of these do you know?
•  » » 11 months ago, # ^ |   +92 Dear ScarletS,How dare you insult the almighty arujbansal by thinking that he may not be aware any of these trivial (for him) topics.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +29 Facts. arujorz _/\_
•  » » 11 months ago, # ^ |   +71 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)
 » 11 months ago, # |   +353 I believe all these things can be learned from some blog posts or talking with top performers except how Elegia's mind works
•  » » 4 months ago, # ^ |   -28 then talk with Elegia
 » 11 months ago, # |   +462 meanwhile some random chinese 8 yr child : "ha ? These all are well known standard tricks since 1969".
•  » » 11 months ago, # ^ |   -32 Lmao
•  » » 11 months ago, # ^ |   +31 What happened in 1969??
•  » » » 11 months ago, # ^ |   +118 Good you aren't asking about 1989.
•  » » » » 11 months ago, # ^ |   +45 What happened in 1989 ?
•  » » » » » 11 months ago, # ^ | ← Rev. 2 →   +49 this comment was deleted by the Chinese government.
•  » » » » » » 11 months ago, # ^ |   0 Stop.
•  » » » » » 11 months ago, # ^ |   -22 This comment has been removed for violating the state law of one or more countries.
•  » » » » » 7 months ago, # ^ |   0 Chinese Lost brutally
•  » » » » 11 months ago, # ^ |   0 DANGER
•  » » » » 11 months ago, # ^ |   -10 The first IOI competition. That's enough.
 » 11 months ago, # |   +299 Yay, I don't know any of these. See you guys in top 10.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 You are also Genius OFZ sir.....
 » 11 months ago, # | ← Rev. 2 →   +50 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
 » 11 months ago, # |   +24 I don't know any of these :)
 » 11 months ago, # |   0 $4\Rightarrow 5$
•  » » 11 months ago, # ^ |   +6 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.
 » 11 months ago, # |   +135 If you only don't know how Elegia mind works, does it mean that you know how everyone else's minds work?
•  » » 4 months ago, # ^ |   -36 then please tell me how my gf's mind work lol
 » 11 months ago, # |   -87 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.
•  » » 11 months ago, # ^ |   +133 Obviously it's in the context of learning them for CP, whataboutism sucks.
 » 11 months ago, # |   +14 ...And this list is bigger than the list of topics I know!
 » 11 months ago, # |   +48 How Elegia's mind works Teach me how to be
 » 11 months ago, # |   +45 I know most of the things from here. Maybe I am doing it all wrong from the start :"(.
•  » » 7 months ago, # ^ |   -10 No difference in red and orangeask the color blind person
 » 11 months ago, # |   +1 oh you are right, but i have to say that many things in this list are well known in chinaalthough they aren't red
•  » » 11 months ago, # ^ |   0 So as he said, they are doing them wrong.
•  » » » 7 months ago, # ^ |   +10 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
 » 11 months ago, # |   +22 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?
•  » » 11 months ago, # ^ |   +11 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.
•  » » » 11 months ago, # ^ |   +40 Arguably, just building suffix automaton with suffix links is a very direct way to build suffix tree.
•  » » » 11 months ago, # ^ |   +172 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.
•  » » » » 11 months ago, # ^ |   +123 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).
•  » » » » » 11 months ago, # ^ |   +191 Turns out that one LGM was enough.
•  » » » » » 11 months ago, # ^ | ← Rev. 2 →   +11 Do you mean this $O(n^3)$ algo? Or is there any simpler approach?
•  » » » » » » 11 months ago, # ^ |   +46 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]}$).
•  » » » » » » » 11 months ago, # ^ | ← Rev. 2 →   +20 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?
•  » » » » » » » 11 months ago, # ^ |   +8 newbies be like how to read this symbol ;)
•  » » » » » » 11 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 $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.
•  » » » » » » » 10 months ago, # ^ |   0 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.
•  » » » » » » » » 10 months ago, # ^ |   +38 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}$
•  » » » » 11 months ago, # ^ |   +68 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.
•  » » » 11 months ago, # ^ |   +54 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.
•  » » 11 months ago, # ^ |   +11
 » 11 months ago, # |   +463 Dude, I'm not having fun solving problems, I'm having fun learning useless algorithms. Get lost.
 » 11 months ago, # | ← Rev. 2 →   +69 For what it's worth, I have seen these: Segment Tree BeatsLink-cut treeDominator treeVoronoi diagram / Delaunay triangulationOperation on formal power series (exp, log, sqrt, ...) (I know the general idea of Newton method)How to actually use generating functions to solve problemsMatroid 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.
•  » » 11 months ago, # ^ |   +8 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.
•  » » 11 months ago, # ^ |   +51 Guilty as charged if you're talking about Grim Treaper
•  » » » 11 months ago, # ^ |   +8 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.
 » 11 months ago, # |   +98 But you know math. Thats enough.
 » 11 months ago, # |   +30 Request: A list of topics you know.PS: I didn't know any of these.
 » 11 months ago, # |   -45 Ok, but do you know about cheaters?
 » 11 months ago, # |   -16 Can you also post about the things you know which is enough to be a LGM -_-??
•  » » 11 months ago, # ^ |   +29 If there would have been a list of algorithms and data structures to learn for becoming LGM, then everyone will be LGM!
•  » » 9 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.
 » 11 months ago, # | ← Rev. 2 →   +180 Things I know Segment Tree Beats RMQ in $O(n)/O(1)$ Any self-balancing tree except treap (Splay) Link-cut tree Mergesort tree k-th shortest path Minimum arborescence (directed MST) in $O(E\log V)$ Halfplane intersection Matroid intersection Things I can copypaste Dominator tree Matching in general graph Weighted matching in general graph Voronoi diagram / Delaunay triangulation Operation on formal power series (exp, log, sqrt, ...) (I don't know the general idea of Newton method lmao) Convex hull in 3D (Quadratic) Things I don't know Li-Chao Segment Tree Wavelet tree (afair trivial things) Binomial heap (But I know randomized mergeable heaps) Fibonacci heap (Ditto) Leftist heap (Ditto, though some of my friends use Leftist instead, cuz the name is cool) 3-connected components in $O(n)$ Preflow-push MCMF in polytime Suffix tree Online convex hull in 2D 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 (Also very interested) Sweepline Mo (What's this??) Btw folks, don't be fooled on last sentence. Knowing them is much more important and interesting than stupid internet points.
 » 11 months ago, # | ← Rev. 3 →   +60 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.
•  » » 11 months ago, # ^ |   +52 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.
•  » » » 11 months ago, # ^ |   +22 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).
•  » » 11 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 :-(.
 » 11 months ago, # |   -20 You forgot 'English' :)
 » 11 months ago, # |   +132 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.
•  » » 11 months ago, # ^ |   +176 KMP and SCCs, what the actual duck XD?
»
11 months ago, # |
+128

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:

•  » » 11 months ago, # ^ |   0 From Where I can access G.M. tourist streams?
•  » » » 11 months ago, # ^ |   0
•  » » » » 11 months ago, # ^ |   0 Thank you
 » 11 months ago, # |   +143 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.
 » 11 months ago, # |   -33 Things you know that no nutella knows: How to get married
•  » » 11 months ago, # ^ |   +9 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?
•  » » » 11 months ago, # ^ |   -10 are you married tho?
•  » » » » 11 months ago, # ^ |   +84 He is married to Swistakk https://codeforces.com/blog/entry/88729?#comment-771586
•  » » » 11 months ago, # ^ |   -32 I didnt said no nutella can get married im saying no one else has done it. Am i wrong? :thinkingface:
•  » » 11 months ago, # ^ |   0
 » 11 months ago, # |   0 I read the title of this blog expecting the post to be empty.
 » 11 months ago, # |   0 This was probably not a shitpost.
 » 11 months ago, # |   +33 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
 » 11 months ago, # |   +11 This does not apply to ICPC participants, right?
•  » » 11 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.
•  » » 11 months ago, # ^ |   +17 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.
•  » » » 11 months ago, # ^ |   0 3 years in CP and I still do not reach the top 1 in my country. F
•  » » » » 4 months ago, # ^ |   -28 Chinese: What r u dreaming about
 » 11 months ago, # |   +109 uhoh, opps... (in my defense I was red before they moved the cutoff...)
•  » » 11 months ago, # ^ |   +64 Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
•  » » » 11 months ago, # ^ |   +28 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.
•  » » » 3 months ago, # ^ |   +36 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)
•  » » » » 3 months ago, # ^ |   +10 This is mind-blowing!
 » 11 months ago, # |   +87 The more you know, the more you know you don't know. $\newline$ $\hspace{80mm}$ — Master Oogway (probably)
•  » » 11 months ago, # ^ |   +153 I'd have taken this advice into consideration if it was LGM Oogway and not Master Oogway.
•  » » » 11 months ago, # ^ |   -18 ok
 » 11 months ago, # |   +34 Fortunately, Elegia is red, otherwise he should learn something like how to use binary search sinse he obviously know at least 3 things here.
•  » » 11 months ago, # ^ |   +51 I am not sure that he knows how his mind works. I certainly don't know how mine works.
•  » » » 11 months ago, # ^ |   +8 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.
•  » » » 11 months ago, # ^ |   0 He is a Self Aware being, which is why no one can understand his mind.
 » 11 months ago, # |   +39 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 :)
•  » » 11 months ago, # ^ |   +31 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.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   -47 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.
•  » » » » 11 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).
•  » » » » » 11 months ago, # ^ |   -46 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.
•  » » » » » » 11 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.
•  » » » » » » » 11 months ago, # ^ |   -49 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...
•  » » » » » » » » 11 months ago, # ^ |   +9 It's not a matter of wording. Order matters, things out of order are just wrong.
 » 11 months ago, # |   +16 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
•  » » 5 months ago, # ^ |   -89 BUMP.
 » 11 months ago, # |   +47 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!
•  » » 11 months ago, # ^ |   -67 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:
•  » » » 11 months ago, # ^ |   +36 Well, I don't see how that is related to my point...
•  » » 11 months ago, # ^ | ← Rev. 2 →   -33 Umnik orz
 » 11 months ago, # |   -9 If one knows how Elegia's mind works then he will absolutely become red
 » 11 months ago, # | ← Rev. 2 →   +2 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 :)
 » 11 months ago, # |   +9 So this is how grandmasters flex
 » 11 months ago, # |   -37 "Any self-balancing tree except treap". Um_nik Don't you know AVL or Red-Black tree ?
•  » » 11 months ago, # ^ | ← Rev. 2 →   +15 He is already DarkRed
 » 11 months ago, # |   +27 How is he even having time to write shitposts after wedding?? Or I am just overthinking? Lol =D
•  » » 11 months ago, # ^ |   0 is there a blog about his wedding?
 » 11 months ago, # | ← Rev. 3 →   +27 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?
•  » » 11 months ago, # ^ |   +49 Learn how to use binary search
•  » » 11 months ago, # ^ | ← Rev. 2 →   -10 I think you should learn how to use brute force and implementation,and solve div.2B first.
 » 11 months ago, # |   +19 So if someone knows how Elegia's mind works then he/she will absolutely become LGM(?)
•  » » 11 months ago, # ^ |   +2 Maybe leading to a new color revolution
•  » » » 11 months ago, # ^ |   0 Legendary International Grandmaster (?)
•  » » 11 months ago, # ^ |   +66 If someone knows how any mind work they will win dozens of Nobel prize for groundbreaking achievement in neurology.
 » 11 months ago, # |   -41 https://codeforces.com/blog/entry/85638 this is a tutorial on voronoi diagram
 » 11 months ago, # |   +8 I know none of these things and I'm doing it wrong, Spoileram I red?
 » 11 months ago, # |   +11 Sweepline Mo You mean that thing where you process some objects (queries) in some order?
•  » » 11 months ago, # ^ |   0
 » 11 months ago, # | ← Rev. 3 →   -46 Message Deleted
•  » » 11 months ago, # ^ |   +13 Read the last line of the blog again :)
•  » » » 11 months ago, # ^ |   +2 Lol its true :-)
 » 11 months ago, # |   +10 The topic of this blog should be "_Things I don't want to know_"
 » 11 months ago, # | ← Rev. 3 →   -16 Not everyone study to become redUPD- There are some who just likes learning new algorithms. Also read this blog ruban's interview
 » 10 months ago, # |   -8 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
•  » » 10 months ago, # ^ |   +2 Lol, stared. See you in 1.5 years.
•  » » 35 hours ago, # ^ |   -10 good luck
 » 10 months ago, # |   +5 I even don't know what i don't know,how did you come to know what you don't know?
 » 10 months ago, # |   +167 PQ-tree sends greetings
•  » » 10 months ago, # ^ |   +6 sad to see an almost template problem about pq tree appears in the contest as problem I
 » 10 months ago, # |   +8 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.
 » 10 months ago, # |   0 _< bisecting
 » 10 months ago, # | ← Rev. 3 →   +24 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$.
 » 8 months ago, # |   +111 Something thing interesting: RMQ in $O(n)/O(1)$ CSP first Round today make problems about it.
•  » » 8 months ago, # ^ |   +25 In CSP-Senior GroupIt has 18 points out of 100 points(in total)and I only get 9/18.So sad
•  » » » 8 months 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. SpoilerI got 18/18.But I'm in ZJ. Life sucks.
•  » » » » 8 months ago, # ^ |   0 I'm also in ZJ and I probably can not pass the first round...Life really sucks for me...
 » 8 months ago, # |   0 RMQ in $\mathcal{O}(n)/\mathcal{O}(1)$ can use The Method of four Russians to solve.PS: CCF (China) test it in CSP-S2021 pre-round...... It's so difficult.
 » 8 months ago, # | ← Rev. 2 →   +55 advise from the world champion!
 » 8 months ago, # |   +13 I don't know any of those topics, I'm doing it great!
 » 7 months ago, # | ← Rev. 2 →   0 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 :(
•  » » 7 months ago, # ^ |   0 You must have learned 四毛子算法 and your "well" is maybe in very high quality.
 » 7 months ago, # | ← Rev. 2 →   -32 "Any self-balancing tree except treap"You don't know red-black or AVL trees? Anyways, maybe it means you don't need to if using C++ STL to be red. Correct me if I am wrong.
•  » » 7 months ago, # ^ |   +6 thx for the advice
•  » » » 7 months ago, # ^ |   0 Want to add something?
•  » » » » 7 months ago, # ^ |   0 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).
 » 7 months ago, # | ← Rev. 2 →   -19 Thanks for the post.
•  » » 7 months ago, # ^ |   +5 This isn't Facebook
 » 6 days ago, # | ← Rev. 2 →   -24 .