Reconstructing a Solution

Loading...

En provenance du cours de Saint Petersburg State University

Competitive Programmer's Core Skills

7 notes

Saint Petersburg State University

Competitive Programmer's Core Skills

7 notes

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.

À partir de la leçon

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

Rencontrer les enseignants

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

[MUSIC]

Previously we designed an algorithm for

finding the lengths of an optimal increasing subsequence.

Now we're going to show how to find the longest increasing subsequence itself.

For this we are going to store an additional array, showing for

which i not only the lengths of an optimal increase in subsequence ending

of this particular element pi but also the previous element in this subsequence.

Here is our previous code with three small additions.

First of all, we allocate in the array prev in the very beginning,

then in the loop we first initialize prev [i] = -1.

This basically means that at this point we don't have any previous element

in our currently longest increasing subsequence ending at the element i.

Recall that at this point the only increasing subsequence that we

know that ends at the element i consists of just a single element i.

So there is no previous element so prev[1] = -1.

Then, when computing the solution for the top problem

ending at an element i, each time when we find a better solution

through the previous element j, we actually change prev[i] to j.

This basically means that at this point, the longest increasing subsequence

ending at an element i, has j as the second to last element.

Okay, so let's give an example.

Using this example we are also going to show how to uncover a solution.

So what you see here is the result of applying this algorithm to

our sample array, okay?

So we see that the length of an optimal increasing subsequence is equal to 5,

just because 5 is the maximum value in our table T.

In particular since T of 13 is equal to 5, this means that

there is a longest increase in subsequence ending at the element 5.

Okay, so

we're going to unwind our optimal increase in subsequence from right to left.

So we already now its element.

This element is number 13.

So prev of 13 is equal to 9.

This basically means that 9 is the second to last element in this subsequence.

So let's go to element 9.

At this point we have already recovered the last two element of an optimal

increasing subsequence, namely the last element is element 13,

the previous element is element number 9.

To find out the element that goes before the element 9,

we simply look at prev of 9.

It is equal to 5.

Meaning that the previous element is 5.

Then to find out the element that goes before the fifth element,

we look at prev of 5, and so on.

So this way we will uncover the whole optimal increase in subsequence.

We stop this process when we find that prev of our current

element is equal to -1.

This basically means that there is no previous element for

this particular element.

Now let's implement it.

So for this we first need to find the largest element in our table T.

This can be done just by scanning the array T from left to right.

Okay, then what we're going to do is to uncover our optimal solution.

For this, we are going to use the list lis.

So we start with the element k,

where the value of the table T, is maximal.

Then what we are going to do in a loop is the following.

We put k to lis, and then we replace k with prev of k.

And we repeat this process until prev of k is equal to -1.

This means that there is no previous element.

And each time we append the current element k to our

longest increasing subsequence, to the variable lis.

So recall that, in this case,

we actually unwind our longest increasing subsequence from right to left.

So in the end, we need to reverse this sequence and

then to print or to return the result.

Now let me also mention the following interesting fact.

So in fact we do not need the array prev in order to

reconstruct the optimal increasing subsequence.

So recall that the fact that the maximum value in T is equal to 5.

Means that the longest increase in subsequence in our sample array

has lengths 5.

So let's just stand at some position where T is equal to 5.

So what we know is that this is the last element of some longest increase

in subsequence of lengths 5.

But what this means is that the prefix of this longest increase in subsequence,

its length is equal to 4.

And this in turn means that to find the previous element

it is enough to scan the table T from right to left and

to find the position where we have 4 in the table T,

such that the corresponding element of the initial

array A is smaller than the last element of our longest increasing subsequence.

So essentially this means that what we need to do is to find

a pattern like 5, 4, 3, 2, 1 in our table T,

such that the correspondent elements of our initial array are decreasing.

So they are decreasing because we go from right to left.

And this can be done just with a simple scan from right to left,

starting with the last element of the longest increasing subsequence.

Let's now summarize.

By analyzing the structure of an optimal solution for

the longest increasing subsequence problem we realized

that it makes sense to compute the following values.

To define the following set problems.

For every element i from 0 to n-1 we defined lis of i

as the lengths of the longest increasing subsequence ending at an element i.

Using the subprograms we can define the recurrence relation

that allows to express the value for lis of i,

through the values of lis of j, for J small as an i.

Then when we wrote down this recurrence relation we converted

it into recursive algorithms, just by adding minimization,

just by adding a table where we stored all the intermediate results.

Our next step was to convert this recursive algorithm

into an iterative algorithm.

So we just filled in the table T from left to right, one by one.

Okay, and finally, we were able to reconstruct our solution

using some additional bookkeeping information such that for

every subproblem we stored not only it's solution,

not only the length of an optimal solution ending at this particular element, but

also the choice leading to these optimal solutions.

So in this case, this was the previous element in the longest

increase in subsequence ending at the i-th element.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play