Perhaps this will be helpful to some. The reason I'm writing this is that these words are used often, and a lot of people understand them the wrong way. This means that if you read some advice containing these words and misunderstand them, you will walk away with a wrong idea.
- Constructive. Refers to problems where a significant part of the solution is about coming up with a pattern that satisfies some properties, e.g. a grid coloring or a graph. A blatant example is this. "Constructive" does not mean the same as "ad hoc", nor does it mean "a problem where no well-known algorithm is needed", nor "a problem where you have to make observations".
- Doubt. You have a doubt when you are not sure about something. That is, you have a pretty good idea, but something seems strange or a little off. If you have no clue, then it is not a doubt.
- Observation. An observation is a friendlier synonym for words like "theorem", "lemma" and "proposition". It is a (usually relatively short) chain of reasoning leading to a conclusion. "Observing" does not in general mean looking at input/output pairs and noticing patterns.
- Plagiarism, plagiarize. Refers to the act of copying itself, not to its detection. For example, "I solved this problem, my friend plagiarized it from me" is correct, "my friend copied my solution and got plagiarized" is not.
- Plague. A disease. Doesn't have much to do with plagiarism.
- Solution, solve. These kind of have two meanings. Almost every problem in CP has two parts: first, you think, and when you have thought something up, you code. "Solving" primarily refers to the former and only secondarily to the latter. When people tell you to solve more problems, they mostly mean that you have to think more, not implement more. Reading an editorial and then implement the idea they give there is not "solving".
- Subquadratic complexity. Refers to any complexity strictly less than $$$n^2$$$ (formally, any complexity in $$$o(n^2)$$$). This includes complexities in $$$\Theta(1)$$$, $$$\Theta(\log n)$$$, $$$\Theta(n)$$$ etc., not only things like $$$\Theta(n^{1.999})$$$.
- Trivial. Something that does not require any special insight beyond what is already given. It does not necessarily mean "easy" or "simple". For example, it would be valid to say that something is "a trivial FFT problem" if the application of FFT is fairly straightforward. This statement doesn't imply that the problem would be easy for everyone, including beginners who have never even heard of FFT. In a similar fashion, a long calculation is often called trivial if it is all pretty much mechanical.
orz
u misused this word
what is orz?
Complexity: Refers to the inherent difficulty of a problem in terms of there not being a very efficient algorithm that solves it in the general case. The asymptotic running time of a specific algorithm is not a "complexity", and "complexity" is also not a synonym for Landau notation. For example, sorting has subquadratic (time) complexity, but merge sort has subquadratic running time.
so it is the same??
Isn't time (and for that matter, space) complexity simply the asymptotic run time of the program? (worst case, average case, doesn't matter)
It is not the same: one is a property of a problem, while the other is a property of an algorithm. There are sorting algorithms, like bubble sort, whose worst-case running time is not subquadratic. Sorting still has subquadratic complexity though, because there exist faster algorithms.
I think the source of the confusion is that novices usually get introduced to the concept of running time, complexity and asymptotics at the same time, but you can have complexity classes that are defined in terms of exact numbers of operations, not asymptotics. (It just would be pretty model-dependent, so typically this is not very useful when not combined with asymptotic notation.)
Of course, among frequent misuses of words, this one is really frequent, to the point where respected computer scientists might disagree with my characterization (typically they are not working on complexity theory though). However, I still cringe every time I see it.
Can't constructive also mean that you need to print the construction and not just the answer?
So are "dp with restoring the answer" problems constructive?
I'd say yes if it's not trivial
In constructive problems, the construction usually is the answer. You can start with printing one number, but it's usually very easy to find it if you have the construction (e.g. min. number of inversions in a permutation satisfying some rules). Often enough, you figure out both together, but even in that case, you could only print the construction and solve the same problem.
Subquadratic — a complexity such that there does not exist an algorithm of such complexity for converting two numbers from one base to another.(Python devs)
I thought they acknowledge it's existence but think subquadratic is too slow
I think you should explain what ad hoc really means too? It seems to be used as "requiring a large amount of ideas for solving", but in fact the definition of the word itself is only about "a solution specifically made for this exact problem".
How about this misused term $$$O(n \log n) = O(n^2)$$$ but $$$O(n^2) \neq O(n \log n)$$$
I think you meant $$$\subseteq$$$ and not $$$=$$$
Oh, I thought we can just use equal sign for comparing two complexities, as there were several editorials where they used $$$O(f(n)) = O(g(n))$$$.
Well I don't know about big O-s on both sides but yes, it is common to write things like
or $$$2 n \log n = O(n \log n)$$$ or indeed $$$n \log n = O(n^2)$$$.
This is formally wrong, but it is correct in the sense that it is a well-established (abuse of) notation so people know what it means, so it's not really the type of thing i wanted to cover in the blog.
I think this is actually formally correct right? Per Wikipedia definition, $$$f(x) = \mathcal O(g(x))$$$ if there exists some constants $$$M, x_0$$$ such that $$$\forall x \geq x_0, |f(x)| \leq M g(x)$$$. So it's legal to write $$$2n \log n = \mathcal O(n \log n)$$$. I agree using big O on both sides is probably abuse of notation though.
EDIT: I just realized I cited Wikipedia as a source for formality which is a bit ironic. For what it's worth, I've seen this same definition and notation used in several textbooks as well.
I meant "does not use a standard definition of equality", i.e. equality as functions or sets.
Am eu o identitate mai calitativa:
$$$O(N*sqrt(N)*log(N)) = O(n^2)$$$ but $$$O(n^2) = O(N*sqrt(N)*log(N))$$$
What about classic or common or famous task, what word to use for so called tasks which are like on cses ?? what should be cutoff for task to be called as famous task.
I haven't heard people say "famous". Indeed most problems in CSES are classical. I don't know how to meaningfully quantify what the cutoff should be.
I think a lot of people would already use the word standard in situations like this.
Or a well-known
there are people who are misusing the word "racism", i would like to hear your explanations and counterexamples
bump
beer
I remember when dalex used to teach Indians English. He got downvoted tho...
deleted. ironically my own phrasing was bad too :D. to clarify, I meant that if the original blog author would've rephrased his blog to not target a specific group of people, not treat other opinions as invalid, and have a less condesending tone, the reaction naturally would've been much less negative. it was not a comment about the content of that blog, just a joke
That debate was also about prescriptive v/s descriptive grammar to a certain extent, as adamant pointed out in the comments on that blog. The usage of stuff like "question" and "giving exams" stems from regional colloquialisms that arise from translating word-to-word from the native language in context, and the same can be said (to a certain extent) about "doubt", since these words are used "incorrectly" even by teachers (not all of them, though), and students tend to pick up these habits from them.
However I feel like this blog is more about how technical words are being misused and how that leads to misunderstandings. When discussing problems and problem-solving, there are certain well-established (but perhaps unspoken) meanings for certain words/phrases (like "constructive", "observation" and "subquadratic complexity") which leave little/no room for ambiguity and their meanings require a certain level of precision to be understood.
I don't mean to be dogmatic with this, as it is already difficult enough to express yourself in a different language other than your own, but the word plague is used for more things than just a disease.
It can be related to plagiarism in the sense that you can say, for example: "plagiarism is a plague in Codeforces". In the same way as the seven plagues of Egypt appear in the old testament.
Every word has a different meaning if you use it as a metaphor.
As I said I don't mean to be dogmatic, but what I mentioned is the actual meaning of the word not a metaphor. The disease is usually referred as black death.
Merriam-webster
Not the only use, but you can observe a pattern. This word has multiple meanings in different contexts. (Btw there's a legitimate method in chemistry sometimes called "eyemetry" where you compare colour to a standardised colour scale, basically poor man's spectroscopy.)
It's kinda gained this other meaning through usage among people who don't know the original meaning, but yeah, it's kind of a vulgar, pleb usage.
Thanks for telling, I usually misuse the word constructive for like where you make the observations.
Give me contributions: Actually means "downvotes me please".