I'm Errichto, and this is a guide on how to start with competitive programming.
In short, Competitive programming is a mind sport or a sport where you need to quickly
implement solutions for some mathy puzzles, some tasks/problems.
There are some big on-site competitions with prizes like Google Code Jam and I will talk about them more in next episodes.
But now let's focus on online platforms and there are plenty of them, but two main ones are
Codeforces.com and atcoder.jp, this is a Japanese website.
But let's focus on codeforces, if you want to start with competitive programming
You should solve easy problems first. In codeforces, you can go to problem set
Sort by difficulty, In some platforms, You can sort by the number of people who solve the problem
That would be the last column here but codeforces
has the difficulty rating, so it's even better. This is decreasingly,
I want increasingly and now this is a trap because some problems aren't rated at all!
I need to scroll and switch to the second page, easiest one has difficulty of
500, whatever that means, let's open that.
In there is a problem statement, usually story or just math definition
Input section, output section. Your goal is to write a program
which will solve this problem, if that program is given this input
It should print exactly this
Some example of a problem would be you need to read user name and
print "hello, name" and then it would need to be exactly this character by character
You cannot make any typos because then you will be judged as wrong answer, after we are done with a program we submit that
to this judge, to this online platform and after a few seconds
We will get result of accepted or some error.
Like wrong answer or time limit exceeded, if we used too much time. Below problem title
there is time limit of 1 second and memory limit of
256 megabytes, you cannot exceed that. In easy problems, you shouldn't worry too much about the time and memory limit
You should just focus on the statement and writing a correct code, efficiency isn't that important. This problem statement says a little girl
has a number and applies the following algorithm, if the last digit of that number is nonzero
She decreases the number by 1, for example from 17 down to 16, if the last digit of the number is 0
She divides the number by ten, then I guess for example from
You're given the initial number n
Tania will subtract using this algorithm, 1 from this K times, You need to print the final result.
For example if initial number is
512 and K is equal to 4, we need to repeat 4 times
the answer should be 50 and most of the time there is
example explanation below, if you are confused how we should get 50 here.
The first example corresponds to the following sequence, from 512 we get to 511, 510, 51, here
something is divisible by 10, So we just removed the last digit than 50
and 50 happens after four steps, so we print 50. Let's see how a program for that looks like
You can open your favorite editor, For me it's geany and I will use C++.
C++ is the main language for competitive programming followed by Java and Python.
But those two are less efficient and less convenient in terms of data structures already available while
C++ has a lot of them in STL library, but if you know Python
It's okay to solve easy problems with Python. You need to read from the input, So after creating two variables n and k
I will read them
and If I was asked about the sum of two numbers
I would print that and this would be a good code, but I need to do something else, repeat k times,
Repeat k times
Change n, if n is divisible by 10 and you can check that in C++ like this, then divide it by 10
Subtract 1, at the end print N. It doesn't matter if you put a new line after that. I can compile this and run
If I put
I should get 50, indeed this is 50.
I can also test on the second test, copy this or hit copy button over there,
Paste and I got 1, just as expected so I can submit.
There is a button for that on the right, choose file
I will choose that from my directory, then submit and now I need to wait for verdict.
The platform has some set of tests
Maybe 50 of them, maybe 100, prepared by all organizers in advance and now they are run automatically like unit tests.
The verdict is accepted.
Let's also try something wrong what happens if I change this to, n/=100?
Maybe I made a typo or something like that. Let's submit this again, I don't actually need to rechoose the file.
Let's refresh this because I don't see myself, as you see a lot of people are using the platform at the same minute
But this is my submission
It's now running on test 1, I can open this submission here, Let's say in the new card
This is some information about it and code, I got wrong answer on test 1.
I can open it and get some additional information
Wrong answer, expected 50, found 4.
The platform will tell you a little bit about your code, at least in terms, at least some platforms do that for your convenience
Some other platforms will just tell you wrong answer and you don't know what is wrong, something is. This is not the only way to
implement a solution for this code.
You can see now on the screen a few solutions in C++ and now a few solutions in Python, There's a variety of them
and something that simple as reading the input can actually be done in different ways
And this way to read input isn't the most efficient one and in some harder problems
I couldn't use this method, if the input could contain a lot of numbers, then using cin isn't fast enough.
There are those details, but again, they do not matter in easy problems. So how to start with competitive programming?
You should first know some language like C++, Java or Python perfectly. It should be C++
If you don't know that first, learn the language, Google some online course or buy a book.
Then you can go to codeforces.com, problem sets, sort by difficulty increasingly, go to that second page to get rated problems
and starting from the easiest ones, solve a lot of them, 20, 100.
Actually if you are bored and this is too easy for you
then you can jump to harder problems, scroll down go to problems with difficulty of 800
or 1000, what if you are stuck in some problem, then on the right most of the time there is section, tutorial
Something written by contest organizers where you can, for this problem wrong subtraction, open tutorial
there will be description of a solution, some analysis
and sometimes code as well.
Here I can see that this is how they implemented this solution, below the tutorial there is often some
discussion and comments about problems, Maybe if you are confused by something, You can go there and search for answer to your question.
I also mentioned another platform Atcoder, there
you can go to some recent contests like Atcoder beginner contest #159
and in terms of those difficulties, you can start with things of difficulty 100 and 200, 300 and 400 will be too hard for beginners.
Go to tasks, open them, and again, there is some statement, input and output description.
After you're done, at the bottom submit your code here, we can copy-paste it and choose the language.
The list of languages is always very big
but 99% of people use C++, Java or Python.
Solving problems is the main thing you should do but also it's nice to read something about
competitive programming to understand what other people do and what you are doing wrong and there is a free book for that online.
"Competitive Programmer's Handbook", the link for that and other things I mentioned will be in the description of the video.
There is some big contents list
and Introduction says, the purpose of this book is to give you a thorough introduction to competitive programming
It is assumed that you already know the basics of programming but no previous background in competitive programming
is needed and the book starts with some
introduction like that
Example of C++ code template, with explanation what it does line by line
Macros, something that other people often do to simplify their code, the refresher on mathematics like summing up squares
or Arithmetic series, Logic, OR, AND, XOR and so on.
Then there are, much later, there are actual algorithms like merge sort or time complexity
insert things, what are data structures? What is a segment tree? and so on and so on, my recommendation is to mix
Reading this book with solving codeforces problems sorted by difficulty. That's it for today.
Thank you all for watching and see you in next episodes where I will talk more about big on-site competitions like Google
Code Jam and those smaller online contests like codeforces rounds and atcoder rounds and you will learn a bit more about this world of
Competitive programming, Bye Bye. :)