Editorial for IOI '15 P4 - Horses - Olympiads Online Judge

Editorial for IOI '15 P4 - Horses

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.

To solve the first subtask, we need to just calculate our answer using dynamic programming.

$dp[i][j]$ $d p [i] [j]$ - what is the maximal profit if we pass $i-1$ $i - 1$ days and we have $j$ $j$ horses, then we got $j \times x_i$ $j \times x_{i}$ horses and check all number of horses that we sell today and go to the next day.

Observation 1

First of all, let's consider two points $i$ $i$ and $j$ $j$ . What if we sell $k$ $k$ horses in the $i^\text{th}$ $i^{th}$ and $j^\text{th}$ $j^{th}$ day? And check which day is more profitable.

Profit of $i^\text{th}$ $i^{th}$ day: $x_1 \times x_2 \times \dots \times x_i \times y_i$ $x_{1} \times x_{2} \times \dots \times x_{i} \times y_{i}$

Profit of $j^\text{th}$ $j^{th}$ day: $x_1 \times x_2 \times \dots \times x_i \times x_{i+1} \times \dots \times x_j \times y_j$ $x_{1} \times x_{2} \times \dots \times x_{i} \times x_{i + 1} \times \dots \times x_{j} \times y_{j}$

It depends on this:

$\displaystyle \begin{align*} y_i &\mathrel{?} x_{i+1} \times \dots \times x_j \times y_j \\ &> \\ &< \\ &= \end{align*}$ $\begin{aligned} y_{i} & ? x_{i + 1} \times \dots \times x_{j} \times y_{j} \\ > \\ < \\ = \end{aligned}$

if it's $>$ $>$ then it's more profitable to sell horses in $i^\text{th}$ $i^{th}$ day
if it's $<$ $<$ then it's more profitable to sell horses in $j^\text{th}$ $j^{th}$ day
if it's $=$ $=$ then it doesn't matter if we sell them in $i^\text{th}$ $i^{th}$ day or in $j^\text{th}$ $j^{th}$ day

From this point, it's clear that it is better to sell all our horses in one day that gives us maximal profit.

Using this observation, we can solve 2 subtasks.

After each query, we can solve the problem in $\mathcal O(n)$ $O (n)$ .

Observation 2

If all $x_i \ge 2$ $x_{i} \geq 2$ , then after $30$ $30$ days, $x_i \times x_{i+1} \times \dots \times x_{i+29} \ge 2^{30} > 10^9$ $x_{i} \times x_{i + 1} \times \dots \times x_{i + 29} \geq 2^{30} > 10^{9}$ , so position less than or equal $n-30$ $n - 30$ can never be an optimal solution, because even if $y_n-30 = 10^9$ $y_{n} - 30 = 10^{9}$ and $y_n = 1$ $y_{n} = 1$ , $2^{30} \times y_n > y_n-30$ $2^{30} \times y_{n} > y_{n} - 30$ .

It's enough to check only the last $30$ $30$ positions.

Observation 3

The main problem in the last subtask is $x_i = 1$ $x_{i} = 1$ , but in that case, multiplication first $x_i$ $x_{i}$ numbers and $x_{i-1}$ $x_{i - 1}$ is not changed. This allows us to merge consecutive positions with $x_i = 1$ $x_{i} = 1$ . When we merge this position, we should take the maximal $y_i$ $y_{i}$ . So if we do that, it's enough to check the last $60$ $60$ positions, because there can be no more than $30$ $30$ merged $1$ $1$ 's between $30$ $30$ last positions where $x_i \ge 2$ $x_{i} \geq 2$ .

So we can store our state in some structure like set, that provides us information about current merged positions, and some structure that provides us RMQ. So solution per query will be $\log(10^9) \log(n)$ $\log (10^{9}) \log (n)$ . Then to calculate the answer, we can use something like segment tree.

So overall complexity will be $\mathcal O(m \log(10^9) \log(n))$ $O (m \log (10^{9}) \log (n))$ .

Comments

There are no comments at the moment.