Maximum Scalar Product

Loading...

來自 Saint Petersburg State University 的課程

Competitive Programmer's Core Skills

13 個評分

Saint Petersburg State University

Competitive Programmer's Core Skills

13 個評分

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.

從本節課中

COMMON STRUGGLES 2

We continue considering common struggles arising in competitive programming. We start by learning how to prove that a natural greedy algorithm is correct. We also discuss programming languages: what features are most helpful on competitions, and what are the advantages and pitfalls of several frequently used languages. Finally, we study an essential and easy-to-implement data structure: the segment tree.

Proving Correctness7:07

Activity Selection9:47

Maximum Scalar Product6:23

Greedy Ordering6:23

與講師見面

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

Let's now consider the maximum scalar product.

In this case, we're given two sequences of integers of the same lengths namely,

the sequence a of lengths n and the sequence b of

lengths n. What we would like to do is to find the permutation

of the second sequence so that

the scalar product of a with this permutation is as large as possible.

So the scalar product of sequences a0,

a1 and so on,

a and minus one and the sequence c0 of c1 and so on,

cn minus one is defined as just the sum of products a0c0,

a1c1, and so on,

an minus one, cn minus one.

So put it otherwise,

what we would like to do is to pair each element of a with each element of

b with an element of b such that the sum of the product of pairs is as large as possible.

For example, if we're given two sequences two,

three, nine and seven, four,

two, then the optimum numbers that we can get in this case is equal to 79.

This can be revealed by the following as scalar product,

so we pair two,

the element of the first sequence with two,

the element of the second sequence,

then paired with the element three with the element four and finally,

the element seven with the element nine,

I'm sorry it was the element seven, okay?

So the result is 79 and we will soon find the way of finding these particular solution.

So the greediest strategy in this case is again quite natural.

So, the idea is to pair

the largest element of the sequence a with the largest element of the sequence b.

So if we prove that this is

indeed leads to an optimum solutions then we can do the following,

select just optimum, the maximum value of a,

select the maximum value of b, pair them,

remove them from a and b and repeat, okay?

Now, let's prove that all this exists.

The solution where the maximum element of a,

we denote it by ai,

is paired with the maximum element of b,

we denote it by bj.

Okay, so for this consider some optimum solution, okay?

So first of all if it pairs ai and bj and then we are done.

So we know that the existing optimal solution which pairs these two particular numbers.

So now, assume that it pairs ai with some different element of b.

So assume that S looks as follows.

It is ai times bp,

plus aq times bj.

So ai is paired with bp and aq is paired with bj.

What we need to prove is that there still exists some other optimum solution,

which paired ai with bj.

So when there is a natural tweek in this case,

let's just swap these two pairs.

So instead of fast let's consider a solution as prime,

which looks almost the same as S with the only difference instead of using aibp and aqbj,

it uses the following two pairs aibj and aqbp.

So again, we just swap these two pairs instead of pairing these two guys,

we pair with this two guys.

Okay, so what we need to show now is that S prime is not worse than

S. And for this we just subtract the value of S from the value of S prime.

So since these two solutions are almost the

same what is left are only these four products.

So it is aibj plus aqbp,

minus aibp, minus aqbj.

Then it is not difficult to see that it can be rewritten as follows.

It is equal to ai minus aq,

times bj minus bp,

and this is in turn non-negative for a simple reason.

So we know that ai is the largest element of i,

of a, I'm sorry,

which means that ai is at least take aq

just for exactly the same reason bj is the largest number of b,

so which means that bj is greater than bp is at least bp.

So this is a product of two non-negative numbers,

which is so this is non-negative which

finally proves that these give as an optimum solution,

which pairs ai and bj, okay?

So then what remains to be done is to convert that

into an algorithm and we will discuss the algorithm actually.

So what you see here is a simple Python code,

so we first check whether the lengths of the given two sequences A and B are equal,

we then declare the variable which initialize it with zero.

And then while the lengths of A is,

while the rest sum remaining elements in A,

we repeat the following step.

We find two maximum elements in A and B,

we denoted by am and bm.

Then we add their product to the result and

then we remove these two elements from a and b.

Finally, when there are no elements left in a re return the result, okay?

So the running time of this algorithm is what I think

is that bigger often square for simple reasons.

So, at most, there are exactly n iterations of the while loop and inside

every iteration what we need to do is to find

two maximum section and to remove two elements.

And all the separations can be done just by

simple linear scan in a linear amount of work.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取