Editorial for IOI '05 P4 - Birthday - Olympiads Online Judge

Editorial for IOI '05 P4 - Birthday

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.

The task is to find such an arrangement of the children, that the maximum number of seats any child has to be moved is minimized. At first we should note, that there are two classes of possible final arrangements. For example, if we have a permutation $(1,2,3)$ $(1, 2, 3)$ , then child $1$ $1$ can be either a left-hand-side or a right-hand-side neighbour of child $2$ $2$ . The first case will be called counterclockwise arrangement, the second will be called clockwise. In both cases calculations are similar, therefore we will only consider clockwise arrangements. Contestants have to consider both cases and choose the smaller result.

Simple solution

The first idea may be to perform simulations of all possible rearrangements. Let us fix the position of the first child. Now, using the given permutation, we can calculate the final positions (and also the distances of movements) of all the children in $\mathcal O(n)$ $O (n)$ time complexity. Since we have to perform this step for all the possible positions of the first child, the total time complexity is $\mathcal O(n^2)$ $O (n^{2})$ .

Optimal solution

There exists a better solution. We denote by $(p_i)$ $(p_{i})$ the given permutation of the children. Let us consider a final arrangement of the children, where the final position of child $p_1$ $p_{1}$ is $f$ $f$ . To achieve this arrangement, some (maybe all) of the children have to move. We can describe the movement of child $i$ $i$ by a number $d^f_i$ $d_{i}^{f}$ , where $|d^f_i|$ $| d_{i}^{f} |$ is the distance of movement, it is positive if the child moves clockwise, and negative if the child moves counterclockwise. Moreover, we assume, that the children always choose such a direction of movement, that the distance is smaller than in other direction (or choose clockwise if both distances are equal), that is $1 - \lceil \frac n 2 \rceil \le d^f_i \le \lfloor \frac n 2 \rfloor$ $1 - ⌈ \frac{n}{2} ⌉ \leq d_{i}^{f} \leq ⌊ \frac{n}{2} ⌋$ .

Let $S_f = \{d^f_i : i = 1, 2, \dots, n\}$ $S_{f} = {d_{i}^{f} : i = 1, 2, \dots, n}$ . We can treat $S_f$ $S_{f}$ as an alternative representation of the considered rearrangement. Having this representation, we can easily calculate the maximum movement distance using formula:

$\displaystyle R_f = \max(-\min(S_f), \max(S_f))$ $R_{f} = max (- min (S_{f}), max (S_{f}))$

Values of $d^f_i$ $d_{i}^{f}$ depend on the given permutation $(p_i)$ $(p_{i})$ and $f$ $f$ . They can be characterized by the following formula:

$\displaystyle d^f_{p_i} = \min(a,n-a)\text{ where }a = (f+i-1-p_i) \bmod n$ $d_{p_{i}}^{f} = min (a, n - a) where a = (f + i - 1 - p_{i}) mod n$

Moreover, given some representation $S_f$ $S_{f}$ , we can easily compute $S_{f+1}$ $S_{f + 1}$ by "shifting" all elements of $S_f$ $S_{f}$ (i.e. we replace $x$ $x$ by $x+1$ $x + 1$ if $x < \lfloor \frac n 2 \rfloor$ $x < ⌊ \frac{n}{2} ⌋$ and we replace $\lfloor \frac n 2 \rfloor$ $⌊ \frac{n}{2} ⌋$ by $1 - \lceil \frac n 2 \rceil$ $1 - ⌈ \frac{n}{2} ⌉$ ).

Now we are interested in calculating the smallest possible result for all $f$ $f$ 's. Please note that all the representations $S_f$ $S_{f}$ are shifts of one base representation, say $S_0$ $S_{0}$ . Let us denote by $C$ $C$ the maximum number of consecutive (modulo $n$ $n$ ) elements from $\left\{1 - \lceil \frac n 2 \rceil, \dots, \lfloor \frac n 2 \rfloor\right\}$ ${1 - ⌈ \frac{n}{2} ⌉, \dots, ⌊ \frac{n}{2} ⌋}$ not appearing in $S_0$ $S_{0}$ . It can be calculated in linear time.

The result is equal to $\lfloor \frac{n-C}{2} \rfloor$ $⌊ \frac{n - C}{2} ⌋$ . This gives us an algorithm with $\mathcal O(n)$ $O (n)$ time complexity.

Comments

There are no comments at the moment.