If there's one thing that you should know about everything is that it is better as a competition.
Let's talk about competitive programming. Competitive programming has been a semi-popular
topic that has been requested ever since I mentioned osu that one time. Being a programmer
though, I haven't partaken in competitive programming in two years and so I don't consider
myself to be particularly qualified to cover this topic but that's what YouTube is all about and so
if you are good at competitive programming, I have nothing more to say. Competitive programming is
different from the programming done in software engineering - it is technically a sport, and so
unlike in software engineering, there is a way to win. Programs are made to solve very specific or
niche problems with a text input and an expected text output in which the format has to be very
exact. For the problem "A Plus B", the automatic judge inputs a and b and the program is expected
to output a plus b. The test cases could result in a number of statuses: there is WA which is
the sound you make when you fail and AC which stands for a-
ccepted. There's also time limit,
memory limit, what are you doing, etc. This verdict is determined by an online judge and one
of the most popular online judges is the Russian website Codeforces. Now, the first step is to use
a VPN to change my location to the Netherlands. This is not a sponsorship, I am simply IP banned
from what I believe to be accidental server abuse. And then we can select a random problem
statement out of the variety of statements under Codeforces problemset to get started.
Another online judge that exists is called DMOJ which stands for DMOJ: Modern Online
Judge. From here, you can already start to see differences in different online judges.
Codeforces allows you to submit code in its editor or as a file whereas
DMOJ only allows you to submit code in its editor or Minecraft server.
Let's look at the Single Source Shortest Path problem the problem statement is solve the
single source shortest path problem. Basically, given this network of roads and you're at one
point what is the shortest distance possible to get to every other point. In the example,
the road between points 1 and 2 has a distance of 2, and so logically the distance between
points 1 and 2 is 2. The road between points 1 and 3 has a distance of 5, but you can get
there faster by going from 1 to 2 to 3 at a total distance of 2 plus 2 equals 4. Thus,
the distance from 1 to 3 is 4. As for point 4, we can recognize that it is impossible
and therefore give up. The problem statement tells us to put the distance as negative one
in this case because it is impossible to have a distance of negative one just like the impossible
pursuit of getting to point four. This entire process is achieved using Dijkstra's algorithm
which is most of Edsger Dijkstra's legacy. This is a man who lived a human life just like you.
At one point in that human life, he thought to himself how can I get from Rotterdam to the other
city in the Netherlands. After thinking for 20 minutes, he came to the conclusion that you can
get there by going to places that are not there until you get there. This is not the Netherlands.
This is not the Netherlands. Going to other places doesn't mean going to every other place though.
Intuitively, the further you've gone the less likely you're on the shortest path, especially
as you get really far away. Thus, it makes sense to go to places in order of how far away they
are to slowly traverse towards your destination. Say we have the option to either go to Amsterdam
or Utrecht from Rotterdam. The distance from Rotterdam to Amsterdam is about 65 kilometers
whereas the distance from Rotterdam to Utrecht is 55 kilometers. Therefore, we can queue up a move
from Rotterdam to Utrecht with a total distance traversed of 55 kilometers. Now the distance
from Utrecht to Amsterdam is about 40 kilometers. However, the number we're concerned with is not
the distance up ahead but with the total distance traversed thus far. Since Rotterdam to Utrecht was
55 kilometers, Rotterdam to Utrecht to Amsterdam would give us 55 plus 40 kilometers of a total of
95 kilometers which is more than the 65 and so our next move queued is actually Rotterdam to
Amsterdam. Of course, this algorithm is assuming that Dutch computer scientists can teleport
to anywhere that they've been before. From Amsterdam, we can then go to Utrecht. However,
we already know that it is possible to get to Utrecht in 55 kilometers and to get from Amsterdam
to Utrecht is another 40 kilometers on top of the 65 kilometers giving us a total of 105 kilometers
which is longer than the 55 and so we don't do that. Despite there being multiple ways to get
to both of these cities, we have the shortest distances to both Utrecht and Amsterdam. Notice
that this worked out because we're keeping track of the shortest distance to each city so far,
terminating any paths that increase the distance for any city. Notice that this prevents any cycles
from happening as well - you wouldn't go from Rotterdam to Amsterdam back to Rotterdam for
example because the distance from Rotterdam to Rotterdam is zero which will always be less than
the distance taken going back and forth. Now let's say we either have the option to go from
Amsterdam to Groningen, our final destination, Utrecht to Groningen, or Amsterdam to Birmingham.
The distance from Amsterdam to Groningen is 180 kilometers. The distance from Utrecht to Groningen
is also 180 kilometers. The distance from Amsterdam to Birmingham is approximately 600
kilometers. It's apparent that the shortest path from Rotterdam is Utrecht to Groningen,
giving us 55 kilometers plus 180 kilometers or a total of 235 kilometers. We have thus
calculated that it is possible to get from Rotterdam to Groningen in 235 kilometers. Well,
what about the other paths? Well, since we're going in order of shortest path from Rotterdam,
once we've reached Groningen, any other paths that could eventually lead to Groningen will have to be
equal to or greater than 235 kilometers and so we do not care. There is no reason to go
to Birmingham and also it is superfluous to traverse there in the scope of this example.
Dijkstra's algorithm is not a difficult algorithm - it's maybe the second algorithm you learn in
algorithm class after Dijkstra but easier. The implementation is very boring. This is
an adjacency matrix which is a 2D array that holds the distance of the shortest road or edge between
any two cities or nodes. This is the distance array which holds the shortest distance so far
for every node and changes as the algorithm executes. This is a priority queue which is a
queue that sorts itself whenever you put something into the queue such as paths which can be sorted
by distance. And this is Rei Evangelion if she was a fast food employee. Putting it all together. you
just take your node along with its total path distance from your queue, check it with your
currently stored distance of that node, and then enqueue all of its neighbouring nodes, repeating
this process until you get to the destination. If there isn't a specific destination in place,
then just go everywhere and keep it running until you've run out of places to go and things to make
better. This is a metaphor for life but more relevantly for the DMOJ problem. What we're
left with is a set of nodes that all have their shortest distances which is exactly what the
problem is looking for. Congratulations. You are now capable of solving this one specific problem
on DMOJ, which places you in the top 30 percent of DMOJ users. But not every problem is single source
shortest path. What if the problem was bubble sort? Or Sieve of Eratosthenes? Ford-Fulkerson?
Segment tree? Aho-Corasick. Robin-Karp. Link/cut tree. MO. Pollard's Rho. Parallel Nightmare.
Dinic's. Fecto Elfilis. Suffix automata. Fecto Forgo. Slice n' Splice. Zan Partizanne. Russian
Peasant. Prim's and Kruskal's. Suffix automata 2. ZERO. Z. Captain Vul. Convex Hull. Baron Gallic.
Graham Scan. Stable Marriage. King DeDeDe.
This is a list of Kirby antagonists actually.
Indeed, a lot of competitive programming is just memorizing algorithms and their template
implementations. You may find yourself memorizing sweep line algorithm which has a use. Where
competitive programming gets less uninteresting is when we deviate from the templates. Let's look at
the VM7WC '15 #4 Gold - Chain Rule. The problem statement is to solve VM7WC '15 #4 Gold - Chain
Rule. Basically, you once again have a network of nodes and roads with a start point and end point
and a secret surprise middle point! The secret surprise is that you have to go there as well
at some point between the start and the end. However, we don't actually know this middle point,
all we know is the start and the end and so the problem requires us to assume that the middle
point is at whichever point that will maximize the shortest path from the start to the middle
to the end meaning that we have to find the longest shortest path distance. Also this time,
all the nodes are guaranteed to be connected. This is obviously a Dijkstra problem and even
if it wasn't you wouldn't know, would you? We can recall from template Dijkstra that it is
quite easy to get a distance from the start to the end. However, this does not guarantee that
we go out of our way to the furthest middle node, in fact it probably wouldn't in the shortest path.
Not knowing the furthest middle node also means that we can't just run Dijkstra from the start
to the middle and then the middle to the end unless we run Dijkstra for every single mode
and compare which one's the furthest in which case will probably exceed the time limit. It
is here that we must truly understand the Dijkstra algorithm in that it's not an algorithm to compute
a distance between an inherent start and an inherent end but rather the distance array
of any singular node to every other node. This means that the start of your Dijkstra algorithm
can actually be the end of your problem. The total distance can be split into two parts:
from the start to the middle and the middle to the end which, on a bidirectional graph, is equivalent
to the start to the middle plus the end to the middle. We thus only need to run Dijkstra twice:
once on the start node and once on the end node. Summing up the two resulting distance arrays,
we get the shortest distance needed to get from the start to the end while passing through any
singular node. The longest distance in this new distance array thus represents the shortest
distance needed to get from the start to the end while passing through the furthest middle node,
such distance being of course the expected output of our solution - the solution to a problem which
from such a perspective only deviates slightly from the template. The sport of competitive
programming ultimately relies on both an understanding of theoretical concepts and of the
implementations of data structures. I wouldn't consider myself to be particularly athletic,
and in my opinion, most of competitive programming is about as relevant to software engineering as
chess, though it's also as interesting and logically challenging. Even if it's been a
few years though, it always feels at home to be accepted... by the server of an online judge website.