Editorial for IOI '02 P4 - Batch Scheduling - Olympiads Online Judge

Editorial for IOI '02 P4 - Batch Scheduling

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 problem can be solved using dynamic programming. Let $C_i$ $C_{i}$ be the minimum total cost of all partitionings of jobs $J_i, J_{i+1}, \dots, J_n$ $J_{i}, J_{i + 1}, \dots, J_{n}$ into batches. Let $C_i(k)$ $C_{i} (k)$ be the minimum total cost when the first batch is selected as $\{J_i, J_{i+1}, \dots, J_{k-1}\}$ ${J_{i}, J_{i + 1}, \dots, J_{k - 1}}$ . That is, $C_i(k) = C_k + (S + T_i + T_{i+1} + \dots + T_{k-1}) \times (F_i + F_{i+1} + \dots + F_n)$ $C_{i} (k) = C_{k} + (S + T_{i} + T_{i + 1} + \dots + T_{k - 1}) \times (F_{i} + F_{i + 1} + \dots + F_{n})$ .

Then we have that

$C_i = \min\{C_i(k) \mid k = i+1, \dots, n+1\}$ $C_{i} = min {C_{i} (k) ∣ k = i + 1, \dots, n + 1}$ for $1 \le i \le n$ $1 \leq i \leq n$ ,
and $C_{n+1} = 0$ $C_{n + 1} = 0$ .

$\mathcal O(n^2)$ $O (n^{2})$ Time Algorithm

The time complexity of the above algorithm is $\mathcal O(n^2)$ $O (n^{2})$ .

$\mathcal O(n)$ $O (n)$ Time Algorithm

Investigating the property of $C_i(k)$ $C_{i} (k)$ , P. Bucker [1] showed that this problem can be solved in $\mathcal O(n)$ $O (n)$ time.

From $C_i(k) = C_k + (S + T_i + T_{i+1} + \dots + T_{k-1}) \times (F_i + F_{i+1} + \dots + F_n)$ $C_{i} (k) = C_{k} + (S + T_{i} + T_{i + 1} + \dots + T_{k - 1}) \times (F_{i} + F_{i + 1} + \dots + F_{n})$ , we have that for $i < k < l$ $i < k < l$ ,

$\displaystyle \begin{align*} C_i(k) \le C_i(l) &\iff C_l - C_k + (T_k + T_{k+1} + \dots + T_{l-1}) \times (F_i + F_{i+1} + \dots + F_n) \ge 0 \\ &\iff \frac{C_k-C_l}{T_k + T_{k+1} + \dots + T_{l-1}} \le F_i + F_{i+1} + \dots + F_n \end{align*}$ $\begin{aligned} C_{i} (k) \leq C_{i} (l) & ⟺ C_{l} - C_{k} + (T_{k} + T_{k + 1} + \dots + T_{l - 1}) \times (F_{i} + F_{i + 1} + \dots + F_{n}) \geq 0 \\ ⟺ \frac{C_{k} - C_{l}}{T_{k} + T_{k + 1} + \dots + T_{l - 1}} \leq F_{i} + F_{i + 1} + \dots + F_{n} \end{aligned}$

Let $g(k,l) = \frac{C_k-C_l}{T_k + T_{k+1} + \dots + T_{l-1}}$ $g (k, l) = \frac{C_{k} - C_{l}}{T_{k} + T_{k + 1} + \dots + T_{l - 1}}$ and $f(i) = F_i + F_{i+1} + \dots + F_n$ $f (i) = F_{i} + F_{i + 1} + \dots + F_{n}$ .

Property 1: Assume that $g(k,l) \le f(i)$ $g (k, l) \leq f (i)$ for $1 \le i < k < l$ $1 \leq i < k < l$ . Then $C_i(k) \le C_i(l)$ $C_{i} (k) \leq C_{i} (l)$ .

Property 2: Assume $g(j,k) \le g(k,l)$ $g (j, k) \leq g (k, l)$ for some $1 \le j < k < l \le n$ $1 \leq j < k < l \leq n$ . Then for each $i$ $i$ with $1 \le i < j$ $1 \leq i < j$ , $C_i(j) \le C_i(k)$ $C_{i} (j) \leq C_{i} (k)$ or $C_i(l) \le C_i(k)$ $C_{i} (l) \leq C_{i} (k)$ .

Property 2 implies that if $g(j,k) \le g(k,l)$ $g (j, k) \leq g (k, l)$ for $j < k < l$ $j < k < l$ , $C_k$ $C_{k}$ is not needed for computing $F_i$ $F_{i}$ . Using this property, a linear time algorithm can be designed, which is given in the following.

Algorithm Batch

The algorithm calculates the values $C_i$ $C_{i}$ for $i = n$ $i = n$ down to $1$ $1$ . It uses a queue-like list $Q = (i_r, i_{r-1}, \dots, i_2, i_1)$ $Q = (i_{r}, i_{r - 1}, \dots, i_{2}, i_{1})$ with tail $i_r$ $i_{r}$ and head $i_1$ $i_{1}$ satisfying the following properties:

$i_r < i_{r-1} < \dots < i_2 < i_1$ $i_{r} < i_{r - 1} < \dots < i_{2} < i_{1}$ and
$g(i_r, i_{r-1}) > g(i_{r-1}, i_{r-2}) > \dots > g(i_2, i_1)$ $g (i_{r}, i_{r - 1}) > g (i_{r - 1}, i_{r - 2}) > \dots > g (i_{2}, i_{1})$ — (1)

When $C_i$ $C_{i}$ is calculated,

// Using $f(i)$ $f (i)$ , remove unnecessary element at head of $Q$ $Q$ .

If $f(i) \ge g(i_2,i_1)$ $f (i) \geq g (i_{2}, i_{1})$ , delete $i_1$ $i_{1}$ from $Q$ $Q$ since for all $h \le i$ $h \leq i$ , $f(h) \ge f(i) \ge g(i_2,i_1)$ $f (h) \geq f (i) \geq g (i_{2}, i_{1})$ and $C_h(i_2) \le C_h(i_1)$ $C_{h} (i_{2}) \leq C_{h} (i_{1})$ by Property 1.

Continue this procedure until for some $t \ge l$ $t \geq l$ , $g(i_r, i_{r-1}) > g(i_{r-1}, i_{r-2}) > \dots > g(i_{t+1}, i_t) > f(i)$ $g (i_{r}, i_{r - 1}) > g (i_{r - 1}, i_{r - 2}) > \dots > g (i_{t + 1}, i_{t}) > f (i)$ .

Then by Property 1, $C_i(i_{v+1}) > C_i(i_v)$ $C_{i} (i_{v + 1}) > C_{i} (i_{v})$ for $v = t, \dots, r-1$ $v = t, \dots, r - 1$ or $r = t$ $r = t$ and $Q$ $Q$ contains only $i_t$ $i_{t}$ .

Therefore, $C_i(i_t)$ $C_{i} (i_{t})$ is equal to $\min\{C_i(k) \mid k = i+1, \dots, n+1\}$ $min {C_{i} (k) ∣ k = i + 1, \dots, n + 1}$ .
// When inserting $i$ $i$ at the tail of $Q$ $Q$ , maintain $Q$ $Q$ for the condition (1) to be satisfied.

If $g(i, i_r) \le g(i_r, i_{r-1})$ $g (i, i_{r}) \leq g (i_{r}, i_{r - 1})$ , delete $i_r$ $i_{r}$ from $Q$ $Q$ by Property 2.

Continue this procedure until $g(i, i_v) > g(i_v, i_{v-1})$ $g (i, i_{v}) > g (i_{v}, i_{v - 1})$ .

Append $i$ $i$ as a new tail of $Q$ $Q$ .

Analysis

Each $i$ $i$ is inserted into $Q$ $Q$ and deleted from $Q$ $Q$ at most once. In each insertion and deletion, it takes a constant time. Therefore the time complexity is $\mathcal O(n)$ $O (n)$ .

Comments

There are no comments at the moment.