Contest Duration: - (local time) (120 minutes) Back to Home

## F - Paired Wizards Editorial by evima

Assume that $$X$$ casts Spell $$2$$ $$C_X$$ times, as the $$x_1$$-th, $$x_2$$-th, $$\ldots$$, $$x_{C_X}$$-th spells from the earliest. Then, the $$x_i$$-th spell deals $$x_i - i$$ damage to the monster. Therefore, the total damage dealt by $$X$$ is $$S_X - \frac{C_X(C_X+1)}{2}$$, where $$S_X=\sum{x_i}$$.
If we similarly define $$C_Y$$ and $$S_Y$$ for $$Y$$, the problem asks us to maximize $$S_X+S_Y-\frac{C_X(C_X+1)}{2} -\frac{C_Y(C_Y+1)}{2}$$.

Let us classify the tuples $$(a_i,b_i,c_i,d_i)$$ into the five patterns below, based mainly on whether the spell for each wizard is fixed.

1. Neither $$X$$’s nor $$Y$$’s spell is fixed, and they are different
2. Neither $$X$$’s nor $$Y$$’s spell is fixed, and they are the same
3. $$X$$’s spell is fixed, while $$Y$$’s spell is not fixed
4. $$X$$’s spell is not fixed, while $$Y$$’s spell is fixed
5. Both $$X$$’s and $$Y$$’s spells are fixed

When the spell for a wizard is fixed, the contribution of that part to $$C_X, C_Y, S_X, S_Y$$ is constant (so Pattern 5 is excluded from the consideration below, as there is no choice to make). Let us try brute force for the choices in unfixed parts.
In Pattern 1, exactly one of $$X$$ and $$Y$$ casts Spell $$2$$. Here, the contribution to $$S_X+S_Y$$ is the same regardless of which wizard casts it, and it only matters how many times each of $$X$$ and $$Y$$ casts Spell $$2$$ in total, considering the contribution to $$C_X$$ and $$C_Y$$. After deciding the number of casts of Spell $$2$$ for $$X$$, the remaining casts of Spell $$2$$ are for $$Y$$, so there are $$\mathrm O(N)$$ choices to try.
In Pattern 2, let $$k$$ be the number of times $$X$$ and $$Y$$ cast Spell $$2$$ here. Then, it is optimal to do so in the last $$k$$ occurrences of this pattern, because the timing only affects $$S_X$$ and $$S_Y$$ ー not $$C_X$$ or $$C_Y$$ ー and maximizing $$S_X$$ and $$S_Y$$ maximizes the total damage. Again, there are $$\mathrm O(N)$$ choices for the number $$k$$ to try.
For similar reasons, there are also $$\mathrm O(N)$$ choices to try in each of Patterns 3 and 4, so we already have an $$\mathrm O (N^4)$$ brute force solution.

After fixing the choices in Patterns 1 and 2, the optimal choices in Patterns 3 and 4 can be separately determined, and they only depend on the values of $$C_X$$ and $$C_Y$$. Therefore, by pre-computing the optimal uses of spells in Patters 3 and 4 for each $$C_X=0,1,2,\ldots$$ and each $$C_Y=0,1,2,\ldots$$, we get an improved $$\mathrm O(N^2)$$ brute force solution, which is fast enough.

posted:
last update: