Estimating memory used

Arrays

Recall the size of data types we introduced in Lesson 1, e.g. int uses 4 B of memory. When we create an int array of size $N$, we are using $4N$ bytes of memory. Convert this to MB and see if it exceeds the memory limit.

When your program exceeds the memory limit, the judge will give a Runtime Error or Memory Limit Exceeded verdict.

Note: The size of boolean is (usually) 1 B. You can verify this using sizeof(bool).

Strings

Recall that a char takes up 1 B of memory. Strings in C++ can be viewed as an array of characters (though they are slightly more complicated). A string of length $N$ would therefore take up around $N$ bytes of memory.

Summation Notation

The summation notation is defined as follows:

$$\sum_{k=m}^n f(k) = f(m) + f(m + 1) + \cdots + f(n - 1) + f(n)$$

Note the similarity with a for-loop: int s = 0; for (int k = m; k <= n; k++) s += f(k);

For example, $$\sum_{k=1}^5 k^2 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2$$

A famous formula for the sum of integers from $1$ to $n$ is: $$\sum_{k=1}^n k = \frac{n(n + 1)}{2}$$

Another famous formula for sum of squares: $$\sum_{k=1}^n k^2 = \frac{n(n + 1)(2n + 1)}{6}$$

Both of these formulas have been asked in past HKOI heats.

Distances

For now, we consider a 2D (Cartesian) coordinate plane, with the $x$-axis and $y$-axis. We specify a point $(x, y)$ using its $x$-coordinate and $y$-coordinate. The point $(0, 0)$ is the origin (labelled $O$).

Here, we discuss notions of distance between points $A(x_1, y_1)$ and $B(x_2, y_2)$.

Euclidean Distance

This is what we usually mean by "distance" — the length of the shortest path. This is the distance of the line segment $AB$, the shortest path between $A$ and $B$.

$$\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$

The formula can be derived from the Pythagorean theorem.

Manhattan Distance

Also known as the taxicab distance. This measures the length of the path between $A$ and $B$, but every step taken along the path must be horizontal or vertical (i.e. parallel to one of the axes).

$$ |x_1 - x_2| + |y_1 - y_2| $$

Chebyshev Distance

Also known as the chessboard distance. This is the number of steps a king in chess would take to travel between two squares (D110 King Movement).

$$ \max(|x_1 - x_2|, |y_1 - y_2|) $$

Generalizations to higher dimensions

For two points $(p_1, p_2, \cdots, p_n)$ and $(q_1, q_2, \cdots, q_n)$ in a $n$-dimensional coordinate plane,

• Euclidean distance: $\sqrt{(p_1 - q_1)^2 + (p_2 - q_2)^2 + \cdots + (p_n - q_n)^2}$
• Manhattan distance: $|p_1 - q_1| + |p_2 - q_2| + \cdots + |p_n - q_n|$
• Chebyshev distance: $\max(|p_1 - q_1|, |p_2 - q_2|, \cdots, |p_n - q_n|)$

Note on handling Euclidean distance

In the case where integer coordinates are given, it may be helpful to perform computations using the square of the Euclidean distance to avoid floating-point errors. For example, to check if $(x, y)$ is less than $R$ units away from the origin, instead of using $\sqrt{x^2 + y^2} \lt R$, it is more accurate to use $x^2 + y^2 \lt R^2$.