Editorial for Balkan OI '11 P6 - Trapezoids

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.

This is a dynamic programming task, with the fruitful use of well-known data structures. There are various possible approaches with time and memory complexities $\mathcal O(n^2)$ ~\mathcal O(n^2)~, $\mathcal O(n \log^2 n)$ ~\mathcal O(n \log^2 n)~ and $\mathcal O(n \log n)$ ~\mathcal O(n \log n)~.

Every trapezoid is represented by two intervals (one on each horizontal line). We can normalize the coordinates, and get the permutation from $1$ ~1~ to $2n$ ~2n~. This can be easily done by sorting the arrays $a$ ~a~ and $b$ ~b~ (and $c$ ~c~ and $d$ ~d~) in $\mathcal O(n \log n)$ ~\mathcal O(n \log n)~ time, with two additional arrays.

We could make things easier by introducing two dummy trapezoids, one on the left and one on the right side with large coordinates.

Next, we will calculate the size of the maximum independent set. We can define partial ordering by sorting the trapezoids according to the upper left corner $a(i)$ ~a(i)~. Let $max\_ind(i)$ ~max\_ind(i)~ denote the size of the maximum independent set of trapezoids $T(1), T(2), \dots, T(i-1)$ ~T(1), T(2), \dots, T(i-1)~ that contain trapezoid $T(i)$ ~T(i)~. It simply follows:

$max\_ind(i) = max\{1+max\_ind(k)\}$ ~max\_ind(i) = max\{1+max\_ind(k)\}~, where $1 \le k \le i$ ~1 \le k \le i~ and $T(k)$ ~T(k)~ lies completely on the left of $T(i)$ ~T(i)~

This produces an $\mathcal O(n^2)$ ~\mathcal O(n^2)~ dynamic programming algorithm.

In order to get an $\mathcal O(n \log n)$ ~\mathcal O(n \log n)~ solution, we will use a binary indexed tree (cumulative table) data structure. Cumulative tables in logarithmic time perform three operations on the array $x$ ~x~:

for given index $k$ ~k~ and number $m$ ~m~, add $m$ ~m~ to the value $x(k)$ ~x(k)~.
for given index $k$ ~k~, calculate the partial sum $x(1) + x(2) + \dots + x(k)$ ~x(1) + x(2) + \dots + x(k)~.
for given index $k$ ~k~, calculate the maximum value among $x(1), x(2), \dots, x(k)$ ~x(1), x(2), \dots, x(k)~.

Let $cum\_max$ ~cum\_max~ be the cumulative table for maintaining the partial maximums. Traverse the coordinates from $1$ ~1~ to $2n$ ~2n~, and for each left upper coordinate $a(i)$ ~a(i)~, calculate $max\_ind(i)$ ~max\_ind(i)~ based on the maximum value among $cum\_max(1), cum\_max(2), \dots, cum\_max(c(i))$ , while for the right upper coordinate $b(i)$ ~b(i)~, write $max\_ind(i)$ ~max\_ind(i)~ in the cumulative table on the index $d(i)$ ~d(i)~. The final solution is $max\_ind(n+1)$ ~max\_ind(n+1)~.

The second part is more difficult. The quadratic dynamic programming solution is given in the following pseudocode:

num_max_ind[0] = 1;
for i = 1 to n do begin
    num_max_ind[i] = 0;
    for j = 0 to i - 1 do begin
        if ((max_ind[j] + 1 == max_ind[i]) and (a[j] > b[i]) and (c[j] > d[i]) then
            num_max_ind[i] = num_max_ind[i] + num_max_ind[j];
    end;
end;

We will use again cumulative tables for designing an $\mathcal O(n \log n)$ ~\mathcal O(n \log n)~ solution. The main problem here is how to manipulate the partial sums. Namely, for each trapezoid $T(i)$ ~T(i)~, we need to sum the values $num\_max\_ind(j)$ ~num\_max\_ind(j)~ of those trapezoids $T(j)$ ~T(j)~ which are entirely on the left of $T(i)$ ~T(i)~ with additional condition $max\_ind(j)+1 = max\_ind(i)$ ~max\_ind(j)+1 = max\_ind(i)~.

This can be done by considering pairs $(k, k+1)$ ~(k, k+1)~ of two neighboring values $1 \le k \le max\_ind(n+1)$ ~1 \le k \le max\_ind(n+1)~. Using two additional arrays for coordinates and trapezoid indices, we can traverse trapezoids $T(i)$ ~T(i)~ from left to right, such that $max\_ind(i) = k$ ~max\_ind(i) = k~ or $max\_ind(i) = k+1$ ~max\_ind(i) = k+1~. First, we need to carefully preprocess all trapezoids and store the coordinates for each pair $(k, k+1)$ ~(k, k+1)~ in one array (or array of dynamic arrays) in order to keep memory limit $\mathcal O(n)$ ~\mathcal O(n)~. Therefore, we fill the cumulative table with the values for trapezoids with $max\_ind(i) = k$ ~max\_ind(i) = k~, and calculate the value $num\_max\_ind(i)$ ~num\_max\_ind(i)~ for trapezoids with $max\_ind(i) = k+1$ ~max\_ind(i) = k+1~. Instead of resetting the cumulative table for each $k$ ~k~, we can remove the values by traversing the array of indices again.

Since every trapezoid will be added and removed from the cumulative table, the total time complexity is $\mathcal O(n \log n)$ ~\mathcal O(n \log n)~. This reusing of the cumulative table makes this task very interesting.

Comments

There are no comments at the moment.