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.
Alexander S. KulikovVisiting Professor
Alexander LogunovCompetitive Programming Co-coach at SPbSU
Kirill Simonov
