Advanced Data Structures and I/O

Loading...

Из курса от партнера Saint Petersburg State University

Competitive Programmer's Core Skills

7 оценки

Saint Petersburg State University

Competitive Programmer's Core Skills

7 оценки

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.

Basic Data Structures5:44

Advanced Data Structures and I/O7:51

Comparing Languages4:54

Познакомьтесь с преподавателями

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

Now, to where the language really saves a lot of folk.

Let's consider as a Set structure.

It's very natural mathematical concept,

and it could do two operations fast.

First, insert an element,

and second, check if some value is contained in the set.

Of course, you could also append new values to the name it carries,

but there is no way to quickly check if some value is contained.

Only iterating through all elements of the array.

There is an extension, unordered set,

which also stores values in increasing order,

and allows binary search for a value.

For example, a query like

find the greatest element in the set which is less than one billion.

The set without a structure is called unordered set.

In fact, ordered and unordered sets are implemented in completely different ways.

Unordered set is entirely hash table,

and also called a hash set.

So, its operations take constant time,

and if you want to use the hash set for custom class,

you need to implement the hash functions for this class.

An ordered set is internally a binary search tree.

So the operation take a greater time,

and to use set with objects of the custom class,

you need to implement a comparator for this class.

Although the bigger values differ, in practice,

an ordered set is like at most,

two times slower than unordered set.

Because the cost of time,

the bigger of unordered set is much larger.

But both are internally quite involved,

and so operations with them are much,

much slower than operations with usual arrays.

But of course, usual arrays could not do specific operations first.

Another actually very similar structure is

a map or it's also called a dict for a dictionary.

In usual arrays, you could look up values by their keys,

which non-negative integers, smaller than the array size.

And the map, you could look up values by any key.

So, it could be any data type,

string, or a large number, or anything.

And the space of the map a little proportional to the number of elements in it.

In fact, from inside a map is

just a set of keys to each because both the values are attached.

So, maps here inherits property the sets have.

In particular, there are unordered maps also called hash maps,

and ordered maps also called tree maps.

The first are slightly faster and the second allow the binary search for a key.

But both are much slower than usual arrays.

So in fact, the bottom line about sets and maps is

use them only if they could make a session like really faster.

For example, asymptotically from be go off and squared, to be go off and log in.

And if not, then just use usual arrays because operations with them are much faster.

Aside from structures, there are also useful algorithms, available languages.

Probably the most important are fast sorting algorithms.

They sort a sequence of values in the go off and log in time.

There are different algorithms: Quicksort,

Merge sort and so on.

Different algorithms differ not only by performance, but also by stability.

Further, they preserve their order on equal elements.

With standard types, it's not that useful a notion.

If elements differ, then they are not equal.

But with custom classes where objects get compiled by several fields,

elements if found out on sorting could actually be distant.

For sorting elements, you also need to implement

a comparator if you sort objects of custom class.

Another useful thing are various implementations of binary search.

They typically allow the search for a value.

In a sorted array in time, we go off again.

Next, there are random number generators.

They usually work as follows.

There is a special function that sets the seed,

and by default, the seed it is either zero or system time.

And then, next random numbers are generated by using that seed.

And so, if seeds are equal,

then a sequence of random numbers is identical,

and that is useful for debugging.

There are also some useful functions like,

return some other number from a segment,

or randomly shuffle a sequence.

Another important language feature are Input/output tools.

In problems, it may be useful,

not only to read integers or strings,

but also the full line operations.

Read from file until the end of it.

Then, no input size is given.

Read whole lines, keep them formatted in various space characters.

There are formatted outputs like print integers,

and if data is small,

append zeroes or spaces to do pinging without them.

Bring floating point numbers in a format like with fixed number of digits at the points.

With the input and output there is also unusual performance.

The input output operations are rather slow

compared to other operations like summing integers for example.

And some values to the input/output are super slow,

so you need how to do it efficiently.

The main issue is, indeed the operations on files are very slow.

So, it's not a good idea to write the file each time you want to print a number.

Instead, first implementations, use buffers,

temporary array of characters.

And when you print something,

it just gets appended to that array.

And only when this array is large enough it gets written to the file and cleared.

Buffered input/output is excellent in terms of performance.

But sometimes, you don't need to make the operation right away for example,

in interactive problems or in debugging because it's maybe

confusing too if you doubt what happen not very exceptionally done.

And so, there is a special comment,

which just advisable for right away.

It's called flush, and of course,

the more flushes you do, the slower it gets.

So, that's all for the common tools.

In the following three videos,

we'll discuss specifics of C++, Java, and Python.

Be sure to watch to learn for your language as

it's very important to know the specific it falls.

You must watch others to get a wider picture.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play