Editorial for Baltic OI '10 P4 - Matching Bins

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.

Let $s_1, \dots, s_n$ ~s_1, \dots, s_n~ be the input sequence of bins and $s_i \le m$ ~s_i \le m~ for $i = 1, \dots, n$ ~i = 1, \dots, n~. The $k$ ~k~ leftmost bins can be put into the next $k$ ~k~ bins in some order if and only if $2k \le n$ ~2k \le n~ and there exists a permutation $p$ ~p~ of the numbers $1, \dots, k$ ~1, \dots, k~, such that

$\displaystyle s_i < s_{k+p(i)}\text{ for }i = 1, \dots, k \quad (1)$

The solution to the problem is the largest $k$ ~k~ satisfying condition (1). Assume that $k$ ~k~ is a solution and $p$ ~p~ is a permutation satisfying condition (1). Let

$x = \max(s_1, \dots, s_k)$ ~x = \max(s_1, \dots, s_k)~ and $x = s_i$ ~x = s_i~
$y = \max(s_{k+1}, \dots, s_{k+k})$ ~y = \max(s_{k+1}, \dots, s_{k+k})~ and $y = s_{k+j}$ ~y = s_{k+j}~

It is obvious that $x < y$ ~x < y~. Assume that $p(i) = k+jj$ ~p(i) = k+jj~ and $p(ii) = k+j$ ~p(ii) = k+j~. Then

$\displaystyle s_i < s_{k+jj} \le s_{k+j}$ $\displaystyle s_{ii} \le s_i < s_{k+jj}$

Therefore we can modify the permutation $p$ ~p~ such that $p(i) = j$ ~p(i) = j~ and $p(ii) = jj$ ~p(ii) = jj~, and the modified $p$ ~p~ also satisfies condition (1). Let $L(x)$ ~L(x)~ be the number of bins of size $x$ ~x~ in the first $k$ ~k~ bins, and $R(x)$ ~R(x)~ be the number of bins of size $x$ ~x~ in the next $k$ ~k~ bins, that is

$\displaystyle \begin{align*} L(x) &= |\{i : 1 \le i \le k, s_i = x\}| & x = 1, \dots, m \\ R(x) &= |\{j : k+1 \le j \le 2k, s_j = x\}| & x = 1, \dots, m \end{align*}$

Define $R(m+1) = 0$ ~R(m+1) = 0~ and $D(m+1) = 0$ ~D(m+1) = 0~ and

$\displaystyle D(x) = D(x+1)+R(x+1)-L(x) \quad x = m, \dots, 1$

Now we can state that the $k$ ~k~ leftmost bins can be put into the next $k$ ~k~ bins in some order if and only if condition (2) holds.

$\displaystyle D(x) \ge 0 \quad x = m, \dots, 1 \quad (2)$

Values of $L(x)$ ~L(x)~ and $R(x)$ ~R(x)~ can be computed in $\Theta(n)$ ~\Theta(n)~ running time and then checking for the condition (2) takes $\mathcal O(m)$ ~\mathcal O(m)~ time. Therefore for a given value of $k$ ~k~ we can check whether $k$ ~k~ is a solution in $\mathcal O(mn)$ ~\mathcal O(mn)~ time. Moreover, if we already computed the values of $L$ ~L~ and $R$ ~R~ for a given $k$ ~k~ then for $k-1$ ~k-1~ we have to modify $L(k)$ ~L(k)~, $R(k)$ ~R(k)~, $R(2k)$ ~R(2k)~ and $R(2k-1)$ ~R(2k-1)~ only. As a consequence, we obtain an $\mathcal O(mn)$ ~\mathcal O(mn)~ worst case running time algorithm. The required memory is $\Theta(m+n)$ ~\Theta(m+n)~.

We can speed up a bit by recomputing only those $D(x)$ ~D(x)~ that might be changed by decreasing the value of $k$ ~k~.

Comments

There are no comments at the moment.