Editorial for IOI '04 P5 - Farmer - Olympiads Online Judge

Editorial for IOI '04 P5 - Farmer

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 $g_i$ $g_{i}$ be a field or a strip. Denote by $n_i$ $n_{i}$ the number of cypresses in a field or a strip. If we denote by $e_i$ $e_{i}$ the number of olive trees in a $g_i$ $g_{i}$ , we have: $e_i = n_i$ $e_{i} = n_{i}$ if $g_i$ $g_{i}$ is a field or $e_i = n_i-1$ $e_{i} = n_{i} - 1$ if $g_i$ $g_{i}$ is a strip.

Consider now the following KNAPSACK problem: $\max \sum_{i=1}^{n+m} e_i x_i$ $max \sum_{i = 1}^{n + m} e_{i} x_{i}$ , such that $\sum_{i=1}^{n+m} n_i x_i \le Q$ $\sum_{i = 1}^{n + m} n_{i} x_{i} \leq Q$ and $x_i \in \{0, 1\}$ $x_{i} \in {0, 1}$ , where $n, m$ $n, m$ are the numbers of fields and strips respectively.

An optimum solution $x^*_i$ $x_{i}^{*}$ , $1 \le i \le n+m$ $1 \leq i \leq n + m$ , of this problem consists of a subset of $g_i$ $g_{i}$ such that the total number of their cypresses is at most $Q$ $Q$ and the total number of the included olive trees is maximized. However in general $Q' = \sum_{i=1}^{n+m} n_i x_i < Q$ $Q^{'} = \sum_{i = 1}^{n + m} n_{i} x_{i} < Q$ . If this is the case, then there is some $g_i$ $g_{i}$ such that $x^*_i = 0$ $x_{i}^{*} = 0$ and $n_i > Q-Q'$ $n_{i} > Q - Q^{'}$ , for otherwise the optimum solution can be improved by the inclusion of $g_i$ $g_{i}$ , a contradiction. Therefore, adding a chain of $Q-Q'$ $Q - Q^{'}$ cypresses of $g_i$ $g_{i}$ and its $Q-Q'-1$ $Q - Q^{'} - 1$ olive trees to the optimum solution of the knapsack problem above, yields an optimum solution. The KNAPSACK problem can be solved optimally in $\mathcal O((n+m)Q)$ $O ((n + m) Q)$ time by a Dynamic Programming algorithm.

Comments

There are no comments at the moment.