I had a brief conversation with stevenwjy and fonmagnus some days ago regarding whether algorithms used in Competitive Programming are commonly used, or at all used in industries. Their respond were, if I remember correctly and I wish I am not misquoting them, “Mostly not used at all and for some algorithms might be best suit in certain industries meaning you might need to use segment tree in trading (?) but not software engineering.” And I understand their respond, in industry, the challenges are different from competitive programming thus requiring different techniques and approaches to solve them.
Looking at machine learning for example, I see that most of the algorithms and data structure used in CP are absent, and the algorithm/technique that are used in ML like Gradient Descent and Linear Regression is not used in CP at all. Even if Dynamic Programming is used, it is slightly different than what we use in CP. I initially felt devastated at first but at the end I understood that they are totally two different fields requiring different experties.
However I am not sure with the other fields in computer science. Which field do you think has the most similarity with CP? Can you mention where each cp techniques are used in other fields?
I am not by any mean trying to say that competitive programming is useless like some people out there. Certainly it has it own merits specifically in building intuition and improving problem solving skill which certainly help in solving real world problems.
Looks like you already answered your own question.
There isn't a specific field that will be similar to competitive programming. Competitive programming is a sport! If you're looking for fields that develop algorithms/data structures then there are a lot of research positions that work on these.
Well I supposed these techniques (Segment Tree, Convex Hull, Greedy, Shortest Path, etc) are invented by researcher for some purposed, could you tell me their uses in say, Software Engineering or other field of cs?
In general, I don't think you will see many CP-like structures in software engineering.
Of course, this depends on what kind of software engineering you're going to be doing (e.g. graphics rendering engines use a LOT of geometry), but mostly you're going to use the other skills that doing CP helps you develop instead of, say, the algorithms or data structures themselves.
For example, it was quite normal for me (and I guess everyone on this site) to write efficient code the first time around without even thinking about it. I quickly realized that this was not the case for a lot of the juniors (and even some of the mid-level SEs) in my company.
It was quite common to see code to, for example, merge $$$N$$$ hash maps that ran in the order of $$$O((\sum{|A_i|})^2)$$$ instead of the expected $$$O(\sum{|A_i|})$$$. This is a huge problem as unit tests are usually small and small inputs don't expose this kind of problem. If this gets caught during code review, great! Otherwise, you're looking at future performance problems that are going to be reaaallly hard to track down. Doing it correctly the first time is really nice in this regard.
There's also other skills that are really nice to have like being able to speedrun through documentation (i.e. problem statement reading & new topic studying skills from CP) or think about weird edge cases (debugging & proving in CP). These are things that CP forces your brain to get used to. You'll probably also be able to do them eventually anyway after years of hands-on SE experience, but CP helps you get a huge headstart IMO.
tourist sucks!
Hello zxc,I think you're not better than tourist on OI, so you have no qualification to say tourist
sucks
aha Mr.zxc, do you think you are good enough to say this? you even can't cb xjn, because she's got a new one, hahaha!
I actually did an extensive research work about this topic (if algorithms were used in "real life") and I concluded that some of them actually have an application in many industries.
In addition, these algorithms are not only used in programming, in fact the concepts of these algorithms are also used in our daily life unconsciously.
Can you elaborate?
Sure, I will give you a simple example (I would share my work but it's written in Spanish and it's long so it would be kinda of useless).
Imagine you don't have any algorithmic knowledge and you are trying to find a specific word in a dictionary, what would you do?
Obviously you wouldn't go from the start to the end of the dictionary checking if you find the right word because it would take you a lot of time.
Intuitevely you would look for the middle part of the dictionary and check if the words in that page are lexicographically greater or smaller than the word that you are looking for, from that point you can discard one half of the dictionary and keep going until you find your desired word.
We did this process every time we checked for a word in a dictionary even though we didn't know what even binary search is.
This was a simple example but from this point you can think for yourself many other examples.
(Note that my english is not native but hopefully you understood my point).
As a game (and software) dev, some commonly used CP techniques (collected from Problemset filters) in games:
In development, you will be implementing your ideas for the most part. You do not need to know any CP techniques, not even binary search*. So the most valuable skill you can get from CP is implementation imo.
Yes, people write $$$O(n^2)$$$ solutions for things that can be done in $$$O(log(n))$$$. But it doesn't matter for games. You usually work with little data simultaneously and you have a lot of space and time for these solutions*. Modern hardware is very powerful.
I am planning to write some tutorials like this for CPers. Maybe one day, when I have time.
* in most cases (99.99%)
In my opinion, recursion and binary search are commonly used in other programming fields.
But stuff like Segment Trees seems to be useless, because you won't have $$$10^5$$$ queries in the real world.
Also, nobody will ask you to compute something modulo $$$10^9+7$$$.
I think that computing something modulo 10^9+7 is useful.If we can compute the answer modulo many co-prime numbers,then we can use Chinese Remainder Theorem to compute the real answer
Since you posted this anyway, I may add another, maybe even better rationale. Problems with modulo computations are mostly used to circumvent usage of large numbers: should you solve a (combinatorial) problem mod some $$$M$$$, it's suffices to change the modulo operations to some bignum library code and you can compute your "true" value. For CP purposes, this is a redundant step that has two drawbacks: unnecesarily pains the contestants without a prewritten (or slow) bignum library + slows down the code execution, ie. using more computing power of the server and making queue times longer.
To frame it differently, philosophically, the purpose of the code in CP is to convince the problemsetter that you solved their problem. Instead of presenting a solution like in math olympiads (so, by writing a proof with natural language), you encode your proof as an algorithm that they are able to execute on many (hopefully hard) examples, so that when your algorithm gives a correct output on all of them, they are satisfied and give you a credit for solving it. This method of "probabilistic" machine verification enables checking solutions almost in real time.
Giving a combinatorial problem with "compute mod $$$M$$$" (or in probability "give a fraction in a form of $$$pq^{-1} \mod M$$$" instead of a plain double) gives just enough power to the problemsetter to verify whether you found a working solution to a problem, which, if was posed in an engineering/industry setup, could be adapted to give results in a different format (in other words, the hard part -- the algorithmic insight -- is already there).
But you're talking about why we compute values modulo a certain number in CP, while the poster you're replying to was trying to give a reason why that would still be useful even outside of CP (where you would probably need the actual number).
Yes, precisely. And my point is that "modulo problems" are almost never about computing stuff modulo.
For example: say you want to compute number of bitmasks of length $$$2n$$$ with precisely $$$n$$$ occurrences of 0 and 1.
Then interesting part is coming up with formula $$$2n$$$ choose $$$n$$$. In the CP world this would be reported mod large num, but I wouldn't call it a "modulo problem" but combinatorics.
Stanley rightfully wrote that "nobody will ask you to compute something modulo". Then Maxu, in my understanding, interpreted this as suggestion that modulo is useless IRL, and provided a good example why it is in fact not useless. And I make a point that while this is true (modulo can be useful), this is not at all a reason why CP problems have computations modulo. In other words, the response to "nobody will ask you to compute something modulo" is not only "sometimes modulo can be useful" but even more "because they will ask you to compute exact value with bignums".
Sorry if I didn't explain this clearly.
On one hand this is true, but nobody will ask you the value before that modulo thing to begin with
2D Segment Trees/Similar Data structures are used for Geohashing by delivery apps where a lot of people might be ordering at the same time and the queries are like -> fetch the nearest $$$k$$$ restaurants in $$$r$$$ radius from the coordinate $$$(x,y)$$$.
Its also used in game development to show detail in places where its needed and not show too much detail in places where its not needed.
There's many uses of segment trees, here's an example. can read more about Geo Hashing here.
CP is also good if you want to get comfortable in programming overall. Of course most of the algorithms used here will probably never/rarely used in real life still not doing cp because of it is like not reading a novel when you are learning English just because most of the sentences in the novel will probably never be used by you in real life.