Editorial for CEOI '16 P2 - Kangaroo - Olympiads Online Judge

Editorial for CEOI '16 P2 - Kangaroo

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.

A sequence of jumps from $c_s$ $c_{s}$ to $c_f$ $c_{f}$ can be mirrored and thus obtaining a valid sequence of jumps from $c_f$ $c_{f}$ to $c_s$ $c_{s}$ . Due to this symmetry, $c_s$ $c_{s}$ and $c_f$ $c_{f}$ can be swapped such that $c_s < c_f$ $c_{s} < c_{f}$ .

We will add the following definitions:

$A[n][i][j] =$ $A [n] [i] [j] =$ the number of alternating permutations that start ascending, having the first and the last elements $i$ $i$ and $j$ $j$
$D[n][i][j] =$ $D [n] [i] [j] =$ the number of alternating permutations that start descending, having the first and the last elements $i$ $i$ and $j$ $j$
$X[n][i][j] = A[n][i][j] + D[n][i][j]$ $X [n] [i] [j] = A [n] [i] [j] + D [n] [i] [j]$ , (our target)
$Y[n][i][j] = A[n][i][j] - D[n][i][j]$ $Y [n] [i] [j] = A [n] [i] [j] - D [n] [i] [j]$ , (for formal reasons)

Let's consider an alternating permutation of length $n$ $n$ that starts with $i$ $i$ and ends with $j$ $j$ . By removing the left extremity ( $i$ $i$ ) and decreasing all values greater than $i$ $i$ by $1$ $1$ , we'll obtain an alternating permutation of order $n-1$ $n - 1$ . We can infer the following recurrences:

$\displaystyle \begin{align*} A[n][i][j] &= \sum_{k=i}^{n-2} D[n-1][k][j-1] \\ D[n][i][j] &= \sum_{k=1}^{i-1} A[n-1][k][j-1] \end{align*}$ $\begin{aligned} A [n] [i] [j] & = \sum_{k = i}^{n - 2} D [n - 1] [k] [j - 1] \\ D [n] [i] [j] & = \sum_{k = 1}^{i - 1} A [n - 1] [k] [j - 1] \end{aligned}$

In other words, the number of alternating permutations of length $n$ $n$ starting ascending with $i$ $i$ and ending with $j$ $j$ is equal to the number of alternating permutations of length $n-1$ $n - 1$ starting descending with $i, i+1, \dots, n-1$ $i, i + 1, \dots, n - 1$ and ending with $j-1$ $j - 1$ . Similarly for $D[][][]$ $D [] [] []$ .

The above recurrences can be rewritten more conveniently:

$\displaystyle \begin{align*} A[n][i][j] &= A[n][i-1][j] - D[n-1][i-1][j-1] \\ D[n][i][j] &= D[n][i-1][j] + A[n-1][i-1][j-1] \end{align*}$ $\begin{aligned} A [n] [i] [j] & = A [n] [i - 1] [j] - D [n - 1] [i - 1] [j - 1] \\ D [n] [i] [j] & = D [n] [i - 1] [j] + A [n - 1] [i - 1] [j - 1] \end{aligned}$

and from here we obtain:

$\displaystyle \begin{align*} X[n][i][j] &= X[n][i-1][j] + Y[n-1][i-1][j-1] \\ Y[n][i][j] &= Y[n][i-1][j] - X[n-1][i-1][j-1] \end{align*}$ $\begin{aligned} X [n] [i] [j] & = X [n] [i - 1] [j] + Y [n - 1] [i - 1] [j - 1] \\ Y [n] [i] [j] & = Y [n] [i - 1] [j] - X [n - 1] [i - 1] [j - 1] \end{aligned}$

After a few manipulations, we can further derive:

$\displaystyle \underset{n \ge 3, i \ge 3}{X[n][i][j]} = 2 \times X[n][i-1][j] - X[n][i-2][j] - X[n-2][i-2][j-2]$ $\underset{n \geq 3, i \geq 3}{X [n] [i] [j]} = 2 \times X [n] [i - 1] [j] - X [n] [i - 2] [j] - X [n - 2] [i - 2] [j - 2]$

Let's stop for a moment to assess the complexity. The answer can be easily computed in $\mathcal O(N^3)$ $O (N^{3})$ using the above recurrence, but it can be reduced to $\mathcal O(N^2)$ $O (N^{2})$ as follows.

Note the following invariant that is preserved by the recurrence:

$\displaystyle n-j = (n-2) - (j-2) = \text{constant}$ $n - j = (n - 2) - (j - 2) = constant$

This is a key observation that shows the first and the third index of $X[][][]$ $X [] [] []$ will not be independent of each other by repeatedly using the recurrence starting backwards from $X[N][c_s][c_f]$ $X [N] [c_{s}] [c_{f}]$ . Therefore, instead of three independent variables, $(n, i, j)$ $(n, i, j)$ , we'll have only two (since $N-c_f = n-j = \text{constant}$ $N - c_{f} = n - j = constant$ ), so the complexity will be $\mathcal O(N^2)$ $O (N^{2})$ for a proper implementation.

We have one more thing to do, namely handling the corner cases $i \le 2$ $i \leq 2$ :

Copy

Case n mod 2 = 1
    X[n][1][j] = A[n][1][j] = A[n][j][1]
    A[n][j][1] = D[n-1][j][1] + D[n-1][j+1][1] + … + D[n-1][n-1][1]
    A[n][j][1] = A[n-1][1][j] + A[n-1][1][j+1] + … + A[n-1][1][n-1]
    A[n][1][j] = A[n][1][j-1] - A[n-1][1][j-1]
Case n mod 2 = 0
    X[n][1][j] = A[n][1][j] = D[n][j][1]
    D[n][j][1] = A[n-1][j-1][1] + A[n-1][j-2][1] + … + A[n-1][3][1]
    D[n][j][1] = A[n-1][1][j-1] + A[n-1][1][j-2] + … + A[n-1][1][3]
    A[n][1][j] = A[n][1][j-1] + A[n-1][1][j-1]
resulting in
    X[n][1][j] = X[n][1][j-1] - X[n-1][1][j-1], n mod 2 = 1
    X[n][1][j] = X[n][1][j-1] + X[n-1][1][j-1], n mod 2 = 0

We have also:

Copy

A[n][2][j] = A[n][1][j] - D[n-1][1][j-1] = A[n][1][j] = X[n][1][j]
D[n][2][j] = D[n][1][j] + A[n-1][1][j-1] = A[n-1][1][j-1] = X[n-1][1][j-1]
(there is no descending permutation starting with 1)
    X[n][2][j] = X[n][1][j] + X[n-1][1][j-1]

Comments

There are no comments at the moment.