Hi. In competitive programming,
it's crucial not only invent a solution,
but to also implement it.
And that is done in a programming language.
So in this lesson,
we'll identify the most helpful language features,
so we could study them more closely.
We'll also learn specific features and pitfalls of C++,
Java and Python, so you won't be cold.
And you'll see what advantages and
disadvantages different languages have, so you could just follow them.
In this video, we'll start with a common language tools.
To excel in competitive programming,
you should really learn how to operate them in your language.
First, we'll cover standard data structures.
The most basic is an array,
which is a specific size sequence of values.
In an array, we could set or take an element by its index.
That's basically the only thing we could do, but it's quite useful.
And the cool thing is,
addressing element is really fast,
because an array is just a sequence of values memory.
The natural improvement of arrays are dynamic arrays.
They are also called vectors or lists.
With them, you could do all the same as like the usual array,
but you also could change its size.
So it's quite useful when you don't know how many values you need to store beforehand.
And you also could just appoint values one by one at the end of the dynamic array.
However, that's not for free.
A dynamic array takes up about twice as much space as the usual array of the same size.
And the usually array takes about the sum of space of all the elements in an array.
And now the usual structure is a string.
It's in fact just an array of characters in some especific operations implemented for it,
so you don't have to write them yourself.
The most basic operations just move around string parts.
For example, concatenate or sub to strings,
extract a substring from a string,
or find a given substring in a string.
Another kind those which divides these caracters.
The most used tool just splits a string by white spaces,
like a sentence in a list of words.
Another one, strings white spaces from the end of the string.
If they both start query,
it's often useful to convert a number to this one on the presentation.
A string of digits characters, and vice versa,
from a string to obtain an integer,
which is written as a string by digits.
There is also a powerful tool of regular expressions.
You could not just search for a given substring,
but rather search for a much regular pattern.
Although they aren't frequently used on competitions,
but sometimes they help in some hard implementation problems.
Next, there are other structures built on top of arrays.
A bitset is just a sequence of bits.
But if you take an array of Boolean variables,
each variable will take one byte because one Boolean variable takes one byte.
But in a bitset each bit takes exactly one bit,
so that's eight time less memory.
That's because a bitset is in fact an array of integers.
Each consist on several bits,
and all those bits are enumerated as
if those integers where concatenated in a single long line of bits.
And the useful thing is that it not just takes less space,
it could also do operations on the whole bitset faster.
For example, add into bitsets,
or count in once in a one bitset.
Just in about an hour to do that operations with integers.
If arrays do not fit in standard datatypes it's nice to have big integers,
which could help in arbitrary-size.
And in fact they look similar to bitsets,
because a long integers is just a sequence of bits.
There are also arbitrary-precision floating point numbers.
And then, just in fact,
big integers shifted by some power of two.
And problems often arise in the queue structure,
where you put elements to the back and take away elements from the front.
Of course, it could be implemented by arrays,
but it's as good now to have the structure
implemented language to make the code simpler and easier to understand.
If you take away elements and put elements on the front, it could do the stack structure.
It's also useful, for example,
the active function calls from a stack.
And if you allow to put and take elements from both ends it will be a deque,
standing for a double ending queue.
It's more powerful than both stack and queue,
and so in fact, stack and queue
are implemented through deque in languages you're learning.
So, we have covered simple array-like data structures.
In fact, it will be enough for most of the problems.
But there are more complicated ones and we will cover them in the next video.
We will also cover input and output.
