OI Guide for Everyone
Welcome to the world of algorithms!
OI (Olympiad in Informatics) is one of the five major high school subject competitions, and in China it originated from 1984.
ICPC (International Collegiate Programming Contest) is organized by ICPC Foundation (ICPC Foundation) and is the most influential college student computer competition. Since ACM sponsored this competition in the past, many people are used to calling it ACM competition.
This blog aims to provide an overview to the algorithms frequently used in these two series of competitions. Later we would submit more detailed descriptions, and relating assignments, problems for newbies to get yourself into this. Enjoy!
About Algorithms
An algorithm is actually a way to solve a problem. Putting it in a computer is a way to solve a problem with a program.
Give a not so exact example:
Maybe everyone in elementary school knows how to do this question
Method One
Add slowly one by one, the answer will definitely be calculated
Method Two
Use formula
For the same problem, you may have many solutions. Of course, different solutions have different advantages and disadvantages. For example, in the first method in the example, you may think that you will make a mistake, or your mentality will explode. Most people are definitely more willing to use a faster and simpler method to solve the problem. For this problem, it is the second method. It can be seen that the algorithm has advantages and disadvantages.
Computer computing speed is very fast, but there must be an upper limit, about 400-600 million times per second. You might say that it is all that fast anyway, regardless of the pros and cons of the algorithm. Here we have to give another example. NS.
Just sort the n people of different heights from low to high
For the first time you need to find the highest among n people
The second time you need to find the second highest among (n-1) individuals
The third time you need to find the third highest among (n-2) individuals
And so on...
Let's calculate how many times the height needs to be compared when n=10000000 (10 million).
The first time it was 10,000,000 times
The second time it was 9999999 times
The third time was 9999998
Even if it doesn’t need to be the last time, it’s better
In fact, a total of (10000000+2)*9999999=100000009999998 times (about 1 billion billion times)
So how long does the computer need to do? ——Only 2 days
I estimate that someone may wait for 2 days to download the game. No one is willing to wait for 2 days for this kind of boring thing... But some very strong people have come up with some algorithms, such as quick sort, which can only be estimated at the same time. Sorting is done NlogN times. Under the same data of n=10 million, it only takes less than 10 seconds. Computers have not become faster, they are all at the same speed, the algorithms used are different, and the efficiency of solving problems is completely different.