Editorial for DMPG '19 S3 - Chemical Counting Capers

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.

Author: AvaLovelace

We can use a stack to determine which elements each ) n applies to. When we reach a (, we push it onto the stack. When we reach a ) n, we take a ( off the top of the stack and update all the elements from its position to the current position by multiplying them by n. Finally, we can use a map to store the number of atoms of each distinct element in the formula.

For the first subtask, for each update, we can iterate through all the elements involved and update them individually.

Time complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

For the second subtask, we can use a "difference" array $diff$ ~diff~ to keep track of the updates. Initially, $diff$ ~diff~ is filled with $1$ ~1~'s. To multiply all the elements from $l$ ~l~ to $r$ ~r~ by $n$ ~n~, multiply $diff[l]$ ~diff[l]~ by $n$ ~n~ and multiply $diff[r + 1]$ ~diff[r + 1]~ by the modular inverse of $n$ ~n~. Then, after all the updates have been completed, we can calculate the prefix product array for $diff$ ~diff~ to find the numbers by which each element must be multiplied to obtain their final totals.

Time complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Comments

4

vsarca commented on Nov. 1, 2023, 12:14 a.m. ← edit 3 →

If you read the input backwards, this whole thing becomes $\mathcal{O}(N)$ ~\mathcal{O}(N)~ without the need for a difference array. We keep a multiplier which is the cumulative multiplication of all the parentheses multipliers, and store all previous multipliers in a stack so we can restore them after an opening bracket. Whenever an element is read we multiply its value by the current multiplier and add to the total.