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.
Can you also shitpost separately about things only nutella-ish people know pls?
Wow. It seems like I accidentally "milked a nutella".
Last Line : Destruction Level 100
Pretty sure you know what mergesort tree is without knowing that it's called that.
So what is 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.
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.
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.
Ohhh, got it.
Thanks :)
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.
DELETED
Its surprising how GMs don't know merge sort tree. I must be doing something wrong...
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.
Am I doing something wrong if I know merge sort tree?
arujbansal, how many of these do you know?
Dear ScarletS,
How dare you insult the almighty arujbansal by thinking that he may not be aware any of these trivial (for him) topics.
Facts. arujorz _/\_
RIP I'm doing it wrong
I believe all these things can be learned from some blog posts or talking with top performers except how Elegia's mind works
then talk with Elegia
meanwhile some random chinese 8 yr child : "ha ? These all are well known standard tricks since 1969".
What happened in 1969??
Good you aren't asking about 1989.
What happened in 1989 ?
this comment was deleted by the Chinese government.
Stop.
However all previous revisions are available for others,so the modification is useless.
This comment has been removed for violating the state law of one or more countries.
Chinese Lost brutally
<!>DANGER<!>
Yay, I don't know any of these. See you guys in top 10.
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
I don't know any of these :)
$$$4\Rightarrow 5$$$
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.
If you only don't know how Elegia mind works, does it mean that you know how everyone else's minds work?
then please tell me how my gf's mind work lol
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.
Obviously it's in the context of learning them for CP, whataboutism sucks.
...And this list is bigger than the list of topics I know!
Teach me how to be <red if you know this :D
be more confident, < black red.
I know most of the things from here. Maybe I am doing it all wrong from the start :"(.
No difference in red and orange
ask the color blind person
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
So as he said, they are doing them wrong.
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
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?
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.
Arguably, just building suffix automaton with suffix links is a very direct way to build suffix tree.
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.
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).
Turns out that one LGM was enough.
Do you mean this $$$O(n^3)$$$ algo? Or is there any simpler approach?
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]}$$$).
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?
newbies be like how to read this symbol ;)
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.
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.
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:
You can laugh at them for not knowing what a 3rd place rating in CF is.
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.
https://ibb.co/0McZWgt
Dude, I'm not having fun solving problems, I'm having fun learning useless algorithms. Get lost.
For what it's worth, I have seen these:
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.
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.
Guilty as charged if you're talking about Grim Treaper
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.
But you know math. Thats enough.
Request: A list of topics you know.
PS: I didn't know any of these.
Ok, but do you know about cheaters?
Can you also post about the things you know which is enough to be a LGM -_-??
If there would have been a list of algorithms and data structures to learn for becoming LGM, then everyone will be LGM!
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.
Btw folks, don't be fooled on last sentence. Knowing them is much more important and interesting than stupid internet points.
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.
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.
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).
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 :-(.
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.
KMP and SCCs, what the actual duck XD?
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),
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:
How to solve it
The Art and Craft of Problem Solving
Problem Solving Strategies
Olympiad Combinatorics recommended by Evan Chen
Algorithmics France IMO Training Camp 2015
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.
Things you know that no nutella knows: How to get married
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?
are you married tho?He is married to Swistakk
https://codeforces.net/blog/entry/88729?#comment-771586
I didnt said no nutella can get married im saying no one else has done it. Am i wrong? :thinkingface:
https://codeforces.net/blog/entry/88729
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
This does not apply to ICPC participants, right?
Depends on your region. Some regional contests like to spam mindless implementation problems as stoppers, instead of coming up with actual difficult problems.
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.
3 years in CP and I still do not reach the top 1 in my country. F
Chinese: What r u dreaming about
uhoh, opps... (in my defense I was red before they moved the cutoff...)
— Um_nik to Richard Peng
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.
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)
This is mind-blowing!
The more you know, the more you know you don't know. $$$\newline$$$ $$$\hspace{80mm}$$$ — Master Oogway (probably)
I'd have taken this advice into consideration if it was LGM Oogway and not Master Oogway.
ok
Fortunately, Elegia is red, otherwise he should learn something like how to use binary search sinse he obviously know at least 3 things here.
I am not sure that he knows how his mind works. I certainly don't know how mine works.
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.
He is a Self Aware being, which is why no one can understand his mind.
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 :)
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.
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.
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).
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.
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.
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...
It's not a matter of wording. Order matters, things out of order are just wrong.
I know —
I was taught these in a formal course I took. Never used it neither remember them now.
I have spent atleast a day reading blogs/watching videos about -
BUMP.
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!
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:
Well, I don't see how that is related to my point...
Umnik orz
If one knows how Elegia's mind works then he will absolutely become red
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 :)
So this is how grandmasters flex
"Any self-balancing tree except treap". Um_nik Don't you know AVL or Red-Black tree ?
He is already DarkRed
How is he even having time to write shitposts after wedding?? Or I am just overthinking? Lol =D
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?
Learn how to use binary search
I think you should learn how to use brute force and implementation,and solve div.2B first.
So if someone knows how Elegia's mind works then he/she will absolutely become LGM(?)
Maybe leading to a new color revolution
Legendary International Grandmaster (?)
If someone knows how any mind work they will win dozens of Nobel prize for groundbreaking achievement in neurology.
I know none of these things and I'm doing it wrong,
am I red?
You mean that thing where you process some objects (queries) in some order?
Ctrl-F Sweepline Mo
Message Deleted
Read the last line of the blog again :)
Lol its true :-)
The topic of this blog should be "_Things I don't want to know_"
Not everyone study to become red
UPD- There are some who just likes learning new algorithms. Also read this blog ruban's interview
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
Lol, stared. See you in 1.5 years.
good luck
I even don't know what i don't know,how did you come to know what you don't know?
PQ-tree sends greetings
sad to see an almost template problem about pq tree appears in the contest as problem I
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.
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
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
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$$$.
Something thing interesting:
CSP first Round today make problems about it.
In CSP-Senior Group
It has 18 points out of 100 points(in total)and I only get 9/18.
So sad
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.
I got 18/18.
But I'm in ZJ. Life sucks.
I'm also in ZJ and I probably can not pass the first round...
Life really sucks for me...
advise from the world champion!
I don't know any of those topics, I'm doing it great!
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 :(
You must have learned 四毛子算法 and your "well" is maybe in very high quality.
"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?
thx for the advice
Want to add something?
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).
Thanks for the post.
This isn't Facebook
.
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.
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
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
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...
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.
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.
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.
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?
you sound like you're stuck at IGM
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.
...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.
Fortunately, I can solve codeforces problems while on the couch. Anyway, I do appreciate the words.
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).
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.
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.
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 :)
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.
How do I start solving problems if I'm lazy? Asking for a friend
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.
Maybe you should know them so you may beat Geothermal
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.
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.
Thanks for your advice.I'll try:)
I've got:
Oh my gosh I have to learn binary search for sure......