Double-checking

Loading...

Do curso por Saint Petersburg State University

Competitive Programmer's Core Skills

1 classificação

Saint Petersburg State University

Competitive Programmer's Core Skills

1 classificação

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, Scala. We assume that you already know how to write simplest programs in one of these.

Na lição

COMMON STRUGGLES

In competitive programming, there are a lot of things to stumble upon — if you don't know them first! We'll delve into how numbers are represented in computers, identify the most common issues with integer and floating point arithmetic, and learn to overcome them. We'll also discuss how to get stuck less in general, especially when debugging solutions.

Debugging Small Programs5:21

Simplifying Code7:40

Double-checking5:42

Conheça os instrutores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Alexander Logunov
Competitive Programming Co-coach at SPbSU
Kirill Simonov

Until now, we're ready to check our codes ourselves.

Let's talk about what's in the computer to do this work.

But first, let's talk about invariants.

In these codes, we have read our counting loop invariants.

Now, we will generalize this concept.

Invariant is a correct statement about data you're working with.

You don't need to come up with invariants specially.

They always arise naturally.

As a loop invariant,

every invariant corresponds to someplace in your code.

Consider the first example.

Here we have an array of integers.

We simply iterate over it and each time we find a negative element,

we change its sign to the opposite side.

We also compute sum of all elements in array after applying this operation.

In the int, we print the sum.

It is obvious that after the loop,

every element in the array will be non-negative.

That's why we can define the invariant,

which you can see on the slide.

Note that we can't put this invariant before the loop.

Consider the second example.

Here we also have an array of integers.

All we do is read in it,

sort in it, and print in it.

Suppose that functions with the appropriate names do this.

And then we have an obvious invariant after sorting.

When the array is sorted,

all elements in it are in non-decreasing order.

So for every i from zero to n minus two,

ith element of the array must be not greater than i plus one element of the array.

It is reasonable to expect that in the way can code all invariants must be satisfied.

So we can check all of them and if we will find a non-satisfied invariant,

we can conclude that there is a bug near by this invariant.

But checking invariants in two previous examples by hand is a big and unreasonable way.

So let's entrust this work to a computer.

There is one special function in each of the main programming languages.

It is usually called "Assert".

It takes an expression as an argument,

computes it, and throws the an error if the result is false.

For example, the expression two is less than three is always true.

So if we pass it to this function,

it will do nothing,

but the expression two plus two equals five, is false.

Surpassing each of this function leads to error.

With asserts, we can automatically check any calculable expressions,

so we can automatically check invariants.

When we use asserts,

our code is actually checked twice by testing and by checking invariants.

Now a few words about Java.

You can assume that in every language,

an assert behaves like a conditional operator.

If a statement is not true through an exception, certainly,

we use asserts for simplicity,

but in Java assert are checked only with the compilation

key -ea, that means "Enableassertions."

You can use this key on your computer,

but on the server the compilation keys may be different.

That's why on Java,

it's recommended to use the mechanism of exceptions.

Let's see how we can use asserts in our examples.

The first example, we expect that after the first loop of elements will be non-negative.

So we can iterate over all elements and check this assertion for every element.

With the current example,

we expect that after sorting,

all elements will be in non-decreasing order.

So we can iterate over all pairs of

neighboring elements and check this assertion for them.

As it was said earlier, if some assertion fails,

it usually means that there is a bug in the code before this assertion.

Can see that in more complicated situation.

You'll know that your code doesn't work.

For example, you sent it to the testing system and they are saved a verdict wrong

answer and you don't know any test on which your code works incorrectly.

In this case, you can add asserts to your codes

in the same way and just send it to the testing system.

And if you see that your code crash with a runtime error on some test,

it can mean that some assertions have failed.

You can find them one by one.

Command out all asserts except the first,

command out all asserts except the second, and so on.

Unfortunately, in attaining an error doesn't always mean failing of assertion.

There are other cases in which an error can be attained.

Array indexes out of bounds division by zero,

infinite recursion, and so on.

So you should be careful with this method of finding bugs.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2018 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play