Programming-Lessons/day1

Mindset

Although a lot of programming paradigms will disagree with this, a good start point for learning to do competitive programming is to see yourself as modifying a certain state over time. As CP does not heavily emphasize code quality (as you don't touch the code after submitting and getting it accepted), this state can be implemented in a variety of ways, particularly to increase your usage of time.

Before you delve into competitive programming as your gateway into programming, be aware of the consequences that it can have on your code quality as you move forward.

This logically follows from the structure of any given problem: you are given a set of inputs, and you are expected to spit out a stream of output. In a way, you have to use your algorithmic skills to, in some way, transform the input data into the output data.

Variable Declaration

There is a clear difference between accessing and modifying already allocated memory versus initializing memory. Thus, in C++, you have two distinct methods to reference a variable (one upon initizliation and one when you are accessing it later on.)

In order to declare a variable, you use the following syntax:

(type) (variable name);

If you want to both declare and initizlie, you use the following syntax:

(type) (variable name) = (value);

Unless constant, variables can always be changed to reflect the information that you have at the current moment.

For instance, if you are implementing a binary search on an array, your search space will have both an upper and lower bound. This information can be represented by two integers that represent the indices of the array that you need to check.

int left = 0, right = vec.size();

Types

There are 5 main primitive types that you have to understand solidly in competitive programming. These are:

1. int, which is a 32-bit signed integer
2. long long, a 64-bit signed integer
3. boolean , a value which is either true or false,
4. string, a sequence of characters (such as a word),
5. character

I will also enumerate the main data structures from the standard library that you ought to know in the following:

1. vectors - arrays whose size can be increased or decreased
2. sets - data structures that can do insertion, search, and min/max queries in logarithmic time (later),
3. gp_hash_table - can do search and insertion in O(1) time, but cannot do min/max queries (later).

Picking variable names

In general programming, variable names are often an important step in writing code, as they significantly enhance code readability. As this is not an issue in competitive programming, shorter (typically 1-letter) variable names are used far more often. Typically speaking, these are the variable names that are used for their particular cases (in my case):

1. Temporary values - a, b, c, d, x, y, z

2. For loop counters - i, j, k, l

3. Constants (that define the size or length of something) - N, M, K (In general, these constants will be referred to by their letters, so just stick to the ones they give you, don't confuse yourself).)

4. Array indices/pointers (we refer to pointers when they represent indices on an array or data structure, not memory addresses) - *ptr

Further Explanations

As C++ has no runtime (and is only based on a compiler and linker for building), by using the syntax above, the compiler is notified of what type the variable is, and thus what functionality it has or does not have. The type system is a complicated field, and thus here, we will not focus on most of it (just remember why you need to use that particular syntax).

If the compiler can infer what your variable type is (when you both declare and initialize), then you can get away with using the auto keyword. (This is generally discouraged for beginners, as it can lead to some nasty bugs)

Input/Output

The data in virtually all competitive programming contests (except for past USACO Contests) will pipe their input through standard input, and will likewise request that you send your output through standard output. This is fairly simple with the cin/cout interface.

In order for you to use the cin/cout API, you must include the following at the top of the file:

#include<iostream>

Example Analysis

Let us take a look at the following example:

int x;
cin >> x;

What did we just do there? The first part is fairly straightforward; based on the syntax, we know that a new variable was just declared named x.

Now what did the second line do? Although the implementation is more direct in other languages, cin breaks up your input stream into tokens. Each token is essentially a collection of characters without any whitespace in between them.

For instance, if your input stream was the following:

1  2 3 
4 fifth

Your tokens would be "1", "2", "3", "4", and "fifth".

cin takes the next token that hasn't been consumed yet and sets the variable x equal to that value. Note that here, since the variable x has the type 'int,' x will be initialized to the value of the token, the string being parsed as an integer.

If we did the following instead,

string s;
cin >> s;

s would just be the next token.

On initializing variables

Unless you are explicitly going to get the value of the variable from standard input, always consider initializing them along with declaring them, so that they do not acquire garbage values.

cin with multiple variables

In order to input multiple variables in succession, you may write something analogous to the following example:

int first, second, third;
cin >> first >> second >> third;

Note that you can chain the ">>" operators together to input multiple variables. In this case, "first" will be the value of the first token, "second" will be the value of the second token, and "third" will be the value of the third token.

cout

The process for cout is a bit more straightforward. Let us say that we want to print the values of three variables, a, b, c, with a space separating the a and b and a new line separating b and c. Then our print statement would be the following:

cout << a << " " << b << "\n" << c;

This results in the following output:

(value of a) (value of b)
(value of c)

Here, the arrow signs are changed from a ">>" to a "<<". Additionally, as cout does not format your output, so make sure to test if the format of your answer is correct before making any submissions to the judge.

Additional Note about endl

Sometimes, you will see competitive programmers do the following instead of what we wrote above:

cout << a << " " << b << endl;
cout << c;

Unless the problem is explicitly interactive, you should never use this syntax. It is very time-consuming for the program to print to the console, and thus, for the most part, it will store its values in a temporary buffer (which is more efficient), and then dump all the values before the program finishes. I know of times when programmers received a TLE issue on a problem simply when they changed all of their endl to "\n".