During the course, you’ll learn everything needed to participate in real competitions — that’s the main goal. Along the way you’ll also gain useful skills for which competitive programmers are so highly valued by employers: ability to write efficient, reliable, and compact code, manage your time well when it’s limited, apply basic algorithmic ideas to real problems, etc. We start from the very beginning by teaching you what competitions there are, what are their rules, what specifics problems have, how to read problem statements, how to organize your work, and what you should and shouldn’t do. So it’s fine if you’ve never taken part in programming competitions before. We’ll focus on skills essential to competitive programming: inventing solutions and proving their correctness, estimating their running time, testing and debugging programs, how to benefit from structuring code. We’ll also cover basic algorithmic ideas: brute force search, dynamic programming, greedy algorithms, segment trees. On competitions, there are a lot of specific pitfalls, perilous to beginners — but that’s not to worry, as we’ll go through the most common of them: integer overflow and issues with fractional numbers, troubles of particular programming languages, how to get unstuck in general. And, you’ll hone all these skills by solving practice problems, which are just like problems on real competitions. You could use any of the following programming languages: C, C++, C#, Haskell, Java, JavaScript, Python 2, Python 3, Ruby, Rust, Scala. We assume that you already know how to write simplest programs in one of these.
Specifics of Programming Competitions
Loading...
From the course by Saint Petersburg State University
Competitive Programmer's Core Skills
7 ratings
From the lesson
Programming Competitions
We'll begin with introduction to the world of competitive programming — the rules, specialties and helpful tips on taking part in competitions in general. In a separate lesson, we'll learn how to test programs: what kinds of test cases there are, how to organize the search for a bugtest, and particularly a method of automating testing called stress-testing.
Meet the Instructors
Alexander S. KulikovVisiting Professor
Department of Computer Science and Engineering
Alexander LogunovCompetitive Programming Co-coach at SPbSU
Kirill Simonov
In this video, we'll discuss specifics of competitions.
What's the difference of competitive programming to other kinds of programming?
We'll start with what competitions actually are.
So, it's fine if you haven't taken part in them.
Competitions are always strictly timed.
The duration they range from 2 to 5 hours,
but it's always monitor events after a certain time period.
You can take part individually on some competitions,
and in teams in others,
but it's always strictly regulated by the rules.
The most common competitions are individual and sometimes,
for example, it's a team of three members.
But always, individual or team,
you won't get any help from the outside, it's against the rules.
Competition consists of several problems.
They are more or less separate and you should
just solve them one by one. Usually, in any order.
Sometimes, all problems cost equal amount of points.
Sometimes, the harder problems cost more points.
But overall, the more problems you
solve the more points you get and the higher place in the ranking you also get.
There are no jury or to something about what problem is better.
All solutions are tested by automated testing system.
So they are all in identical conditions.
And it also means that you won't get much help from us in getting your solution accepted.
The problems in the competitions are quite specific, so let's discuss them.
First, in contrast to problems
in industry where the problems could always be a little bit,
problems here are always strictly formulated.
It's often done through some real-world legend
which offers motivation and the situation of what's happening.
But it's always some mathematical model,
which underlies the problem and it's always strict because everything done automatically,
the input and the output format and so on,
it's also strictly formatted.
And it's described in the statement of the problem.
Another thing, each problem also has time limit and memory limit.
So a solution must fit in an allocated amount of time,
and it also must not use more memory than is given.
The time limit is usually about 72 and memory limit is like 512 megabytes for example.
So it's really important to pay attention to performance of your program.
And so, often, solve a problem somehow is easier,
but solve it fast enough to fit in the time limit is what's really hard.
And you often need to know some common ideas and algorithms
to be able to invent a right solution and make it fast enough.
Mainly algorithms from basic to advanced in different topics,
we'll cover in other causes of this specialization.
Now, as we know what a problem is, what is a solution to it?
It's actually a program in one of the supported languages.
What language are supported may differ from one problem to another.
Some may be less and some of them may be more languages.
And the most popular asset is C++, Java, and Python.
These languages you'll find mostly anywhere.
And so, we'll give examples during our course in these three languages.
But you can do assignments in several more language also.
And they're talking about short programs.
They're usually about several dozen lines.
Well, the hardest problems may gets like 200 lines at most.
And so, as programs are short,
they're expected to fit in a single file which you will submit through that system.
This program which you write must read input data as text,
in the format described in the statement,
which is like very strictly described.
It should do so from either standard input or from an input file of some fixed name,
which is given in a statement.
The output, as it's check automatically should also be strictly formatted,
and it's also described in the statement.
Use the new program to test your system and here,
it's automatically tested against prepared test case.
Meaning, that there is like several dozen so hundred
of tests and they are getting fit to your program on by one.
Each test, it should solve in a given amount of time,
for example in a second per test.
And you should output a correct answer to it.
Because the solution runs on a remote testing server and not on your own computer.
It's subject to strict regulations.
It should not get to the internet write to other files than the output file,
use additional libraries, and so on.
In the end, your submitted solution receives a verdict,
which is showing you either right after
submission or at the end of the contest depending on the rules.
Usually, the program is either tested until
the first error and that error in shown to you.
So, what types of verdicts there are?
They actually illustrate what does the testing system check about a solution.
The first possible error is compile error.
And that means that your program doesn't compile if you get that.
It also usually tells you a message of the compiler why a program doesn't compile,
because the versions of
the compiler could be different on a testing system and on your computer.
Of course, this error makes sense on
default languages that are compiled for example, C++ and Java.
The next error is runtime error.
It means that your program has crashed on some test.
So it's started working,
started reading tests, and then something wrong happens.
For example, you go all before they balance,
or divide by zero, or so on.
The next kind of error is time limit exceeded.
It means that on some test,
your program just didn't terminate in the fixed amount of time.
So, it worked well and the time ends.
Similar is the memory limit.
If on some tests your program eats up more memory than it's stated in the statement,
then it gets terminated and you're shown the memory limit exceeded target.
If your program didn't crash and did not exceed time and memory limit,
the tested system checks the output.
One kind of error you can get is presentation error.
It means that your output isn't formatted to the rules.
That a system just couldn't check it right.
It doesn't understand it. Another maybe the most common type of error is wrong answer.
It means that your solution successfully exited a vital output,
the output is currently formatted,
but is just not correct.
The final and the best verdict for you is accepted.
It means that all tests were passed, your system didn't crash,
didn't exceed either limit,
and the output was correct in all cases.
You can see that verdicts are tested somewhat sequentially.
You won't get your output even don't get checked,
if you get a time limit exceeded.
And if the format is not correct,
the checker doesn't check that your output is correct by itself.
You are also given a test number with the verdict.
Except of course, where it is like compilation error because it's before any testing,
and accepted because error thus has passed and there's no information on test number.
All other verdicts will show you what test exactly, did the program fail.
And that might be useful for the background.
You could check your progress, or for example,
if you failed on the first test then it's something completely wrong with your program.
Another useful thing to know is what test case could be.
The good thing is there are always a certain specific format.
You have no need of checking some typos, different errors.
You won't need to handle errors like in real life applications, and so on.
You're guaranteed to have the input of specified format.
And its size and range of ideas are also limited by the statement,
so you know what large tests you'll be handling.
However, in the real world,
you can make a lot of useful assumptions about the data.
For example, people's names are usually short and you are
looking such queries are usually similar, and so on.
But on competitions, any assumption about
the data except for what's written in the statement is basically is false.
So, any test which is good enough according to
input format of the statement could be fit to your solution.
And you should be able to solve it.
So probably, not as usually try to get tests of every possible kind,
with every possible extreme condition, or so on.
And usually, competition rules are so
that your solution must pass all tests to get any score.
So it's very important to see some like special or with logical cases to your solution.
In the next video,
we will illustrate all said before with an example problem.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
