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: