Level Up#12800

Level Up (Editorial)

Author:

Stefan Ruseti

Developer:

Adrian Budau

Editorialist:

Adrian Budau

The first idea would be to go through the quests in order and pick whether or not we solve that quest at the first level or at the second level.

We can use dynamic programming for this: dp[i][j][k] to be at quest and have accumulated j experience at the first level and k experience at the second level.

When we are at a state dp[i][j][k] and are deciding what to do with quest i + 1 we might run into this special case: we try to solve quest i + 1 in the first level but we overflow the experience into the second level (j + x_i > S1). We must remember to use the overflow experience at the second level. (so dp[i][j][k] -> dp[i + 1][S1][k + (j + x_i - S1)]).

Unfortunately, we don't exactly try all possible orders to do the quests, and especially the quest that triggers the overflow. We solve quests independently at each level in the order we process the quests. But, there is a simple observation to be made: if in a correct solution we solve the quests (i_1, i_2, i_3, ..., i_K) at the first level in this particular order, we could reorder quests i_1, i_2, ..., i_{K-1} and get a different solution. We can not exactly pick any quest to be the last at level 1.

For example if we have quests we want to do at the first level, giving experience each and giving experience and S1 = 100 the only way to solve them at the first level is to first solve the quests giving each (therefore accumulating experience) and then solving the experience quest. We can see that if we can overflow using a quest giving experience from the list i_1, i_2, \dots, i_K than we can overflow with any quest giving V \geq U experience.

So that means we could set the order of solving the quests: ascendant order by their first level experience (x_i). Now we can use the dynamic programming solution describe above with no other modification.

Total complexity: \mathcal{O}(n \cdot s1 \cdot s2) time and \mathcal{O}(n \cdot s1 \cdot s2) or \mathcal{O}(s1 \cdot s2) (depending on implementation) memory.