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] - what is the maximal profit if we pass i-1 days and we have j horses, then we got 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 and j. What if we sell k horses in the i^\text{th} and j^\text{th} day? And check which day is more profitable.

Profit of i^\text{th} day: x_1 \times x_2 \times \dots \times x_i \times y_i

Profit of j^\text{th} day: 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 \\
&> \\
&< \\

  • if it's > then it's more profitable to sell horses in i^\text{th} day
  • if it's < then it's more profitable to sell horses in j^\text{th} day
  • if it's = then it doesn't matter if we sell them in i^\text{th} day or in j^\text{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).

Observation 2

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

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

Observation 3

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


There are no comments at the moment.