Subproblems Revisited

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

Dynamic Programming

Dynamic programming is a powerful algorithmic paradigm with lots of applications in areas like optimisation, scheduling, planning, bioinformatics, and others. For this reason, it is not surprising that it is the most popular type of problems in competitive programming. A common feature of such problems is that a solution is usually easy to implement. This does not however mean that it is also easy to find a solution! Therefore, it is important to practice solving such problems. And this is exactly what we are going to do in this module!

Subproblems and recurrence relation8:52

Reconstructing a Solution9:02

Subproblems Revisited8:22

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

[MUSIC]

We will now discuss an alternative way

of solving the longest increasing subsequence problem.

It is a common feature of many dynamic programming algorithms,

that the most creative part in designing such

an algorithm is coming up with the right notion of a subproblem.

When we have the right notion of a subproblem and

the recurrence relation for subproblems, it is just a technicality

to convert this reccurence relation into a recursive algorithm.

In the previous part, we were able to find the right way of

defining subproblems by analyzing the structure of an optimal solution.

In this part, we are going to do the same, by actually first

implementing the brute force solution and then by optimizing it, okay?

So what is the most naive way of solving the longest increasing subsequence?

Well, let's just enumerate all possible increasing subsequences,

and let's just select the longest one, right?

So this is once again, the most naive way of solving this problem.

So to implement this idea, let's do the following.

Let's start with an empty sequence,

and at each iteration we are going to do recursively the following thing.

So we have some, initially, the sequence is empty.

And at each iteration, we just try to extend it by every possible element,

just by one element, and then we make a recursive call.

So when also we keep track of the lengths of our current subsequence,

then if it is longer than what is currently known?

Then we update some global variable, for example.

The resulting algorithm is going to be slow.

For example, if our initial array is increasing,

then we will be forced to go through all possible subsequences of this array,

and there are exponentially many of them.

But not to worry, we are going to optimize this algorithm later.

Here is a Python implementation.

So this is a recursive procedure that is going to extend,

optimally, the current subsequence.

Initially, the sequence that would pass to our recursive procedure is empty.

Inside the recursive code, we do the following.

We initialize the following two values, last_index and last_element.

So last_index is the last index of our current sequence.

So if the sequence is empty, then it is just equal to -1.

If it is not empty, then this is just the last element of the sequence.

The last_element is actually the value of the correspondent index.

If the sequence is empty, it is equal to -inf.

If it is not empty,

it is equal to the corresponding element of our initial array A.

Then after initializing these two parameters,

we try to extend our current sequence by one element.

Namely, we go through all possible elements to

the right of our current index.

And if the corresponding element is greater than our last element,

then we append it to our sequence and we make a recursive call.

Okay, now let's start optimizing our code.

So first of all,

a closer look at our code reveals the following interesting property.

In fact, what we do in our recursive procedure is

trying to extend optimally our current sequence.

At the same time we are not interested in what is going on in

the beginning of our sequence.

What we essentially use is its last element, and

the lengths of the current sequence.

So which means that instead of passing the whole sequence to our recursive call.

It is enough to pass its last element, and the index of the last

element of the current sequence, and also its length.

So let's do this, and let's optimize the code.

And here on the slide, you actually see the optimized code.

So in this case, we start by computing the last element,

again just by using the last index.

And then again, we try to extend the current sequence optimally.

By making a recursive call to a sequence for which we append some new element.

So we iterate through all the elements,

through all i that are greater than the last index.

And if A[i] > A[last_index],

we try to append the element i to our current sequence.

So in this case, we increase the length by 1, and

we use i as the last index of our new element.

So, this is to optimized code, so far so good.

In this case, instead of passing the whole sequence, we pass only two parameters,

the last index of our current sequence and its length.

Again, a closer look at the resulting code reveals that in fact,

we are not that interested in the length of the current sequence

in order to optimally extend it.

In other words, no matter what is the length of this sequence,

we are going to extend it, based on its last element, in exactly the same way.

As slightly more formally,

if we subtract x from the seq_lem in this recursive call and

add x to the result, it would give exactly the same.

And this suggests that we just replace seq_len by 0.

And this will give us the algorithm that you see here on this slide.

So basically,

what we did here is just that we replace the sequence lengths with zero.

So again, this is a recursive algorithm, and in general it is going to be slow,

just because it is going to recompute many things again and again.

But we already know how to make it more efficient,

we just need to add memoization.

So for this, we might want to introduce a table t, and

to store all the results that are already computed in the table.

And for each time we make a recursive call,

we first check whether the result is already in the table or not.

So if we add memoization to these recursive procedures,

then what we get is almost the same algorithm that we got before,

in the previous parts.

Okay, now let's summarize.

So the most important message is that the most creative part in designing

dynamic programming solutions is coming up with the right notion of a subproblem.

And there are basically two common ways of finding the right problem.

So the first one, as we illustrated with an example of the longest increasing

subsequence, is analyzing the structure of an optimal solution, okay?

The second one that we've just illustrated in this part is first

implementing the most naive brute force solution, and then optimizing it.

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