Editorial for IOI '04 P1 - Artemis - Olympiads Online Judge

Editorial for IOI '04 P1 - Artemis

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Observation: Let $f(x, y)$ $f (x, y)$ be the number of trees below and to the left of $(x, y)$ $(x, y)$ . Then the number of the trees in the rectangle bounded by $t_1$ $t_{1}$ and $t_2$ $t_{2}$ is:

$\displaystyle f(t_1.x, t_1.y) + f(t_2.x, t_2.y) - f(t_1.x, t_2.y) - f(t_1.y, t_2.x) + 1$ $f (t_{1} . x, t_{1} . y) + f (t_{2} . x, t_{2} . y) - f (t_{1} . x, t_{2} . y) - f (t_{1} . y, t_{2} . x) + 1$

if $t_1$ $t_{1}$ lies below and to the left of $t_2$ $t_{2}$ (or vice versa), and a similar formula if not.

Trivial algorithm. Loop over all rectangles, and loop over all trees to count those inside the rectangle.

$\mathcal O(n^3)$ $O (n^{3})$
Use dynamic programming to compute $f(t_1.x, t_2.y)$ $f (t_{1} . x, t_{2} . y)$ for every $t_1, t_2$ $t_{1}, t_{2}$ . Then evaluate all rectangles using the formulae.

$\mathcal O(n^2)$ $O (n^{2})$ , but also $\mathcal O(n^2)$ $O (n^{2})$ memory
Place an outer loop $t$ $t$ over the trees, representing one corner of a potential rectangle. To evaluate rectangles with corners at $t$ $t$ , one only needs $f(t.x, *)$ $f (t . x, *)$ and $f(*, t.y)$ $f (*, t . y)$ . These can be computed with DP as in algorithm (2), and requires only linear memory.

$\mathcal O(n^2)$ $O (n^{2})$
Sort the trees from left to right, and then process them in that order. As each new tree (say $t_n$ $t_{n}$ ) is added, it is inserted into a list of current trees that is sorted vertically. From this information one can calculate $f(t.x, t_n.y)$ $f (t . x, t_{n} . y)$ and $f(t_n.x, t.y)$ $f (t_{n} . x, t . y)$ for every $t$ $t$ to the left of $t_n$ $t_{n}$ , in linear time. Then one can evaluate all rectangles with one corner at $t_n$ $t_{n}$ . This ends up being very similar to algorithm (3).

$\mathcal O(n^2)$ $O (n^{2})$
Algorithm (1), but with optimised counting. As a pre-process, associate a bitfield with each tree representing which trees lie below and to the right, and a similar bitfield for trees below and to the left. The trees inside a given rectangle may be found as the binary AND of two bitfields. A fast counting mechanism (such as a 16-bit lookup table) will accelerate counting.

$\mathcal O(n^3)$ $O (n^{3})$ and $\mathcal O(n^2)$ $O (n^{2})$ memory, but with low constant factors

Comments

There are no comments at the moment.